题解：P17738 [ICPC 2019 Xuzhou R] Yuuki and a problem

· · 题解

SOLUTION

看到这个题，首先我就想到了 [FJOI2016] 神秘数，这两个题除了带不带修完全一样。

先讲一下那个题的做法。

对于一个询问区间，我们从小到大考虑里面的每一个数，假设当前已经能把 [0,x] 都用子集和表示出来，把这个区间称为答案区间，初始时 x = 0。

设当前考虑到的数是 k，当 k \le x+1 的时候，可以把答案区间扩展到 [0,x+k]。

否则当前区间里不存在一个子集的和为 x+1，答案就是 x+1。

考虑优化这个过程。假如我们能一次把所有 k \le x+1 的和求出来，用于扩展答案区间，会不会更快一些？

具体地，设上一次扩展的答案区间为 [0,lst]，就是要求出所有 k \in (lst+1,x+1] 的和，显然可以二维数点来做。

在复杂度证明上，一次有效扩展至少会把答案区间扩展到 [0,x+lst+2]，然后令 lst = x，这是一个类似斐波那契数列的增长，易知他只会扩展 \log V 次就会顶到头，其中 V 是值域。

不带修的话，可以用主席树实现二维数点，容易做到 O(N \log N + Q \log N \log V)。

回到本题，显然可以直接上树套树飞过去，但是树套树的二维查询是 O(\log ^2 N) 的，加上迭代的 \log V 次，一共达到了三只老哥的复杂度，这无疑是会被卡飞的，况且我不会写树套树。

考虑优化不带修时的做法，使其更易维护。

将区间倍增地划分为 \log V 段，具体地，第 k 个区间是 [2^{k-1},2^k)。

重现原迭代过程，设当前已经考虑完前 k-1 个区间里的所有数，当前答案区间为 [0,x]。

找到区间 k 内最小的一个数 y，如果有 y > x+1 则退出，答案为 x+1。

否则加入 y，答案区间扩展为 [0,x+y]。显然有 x,y \ge 2^{k-1}，即 x+y \ge 2^{k}，也就是说，值域区间 k 的最小值若能被加入，那整个区间都能被加入。

于是在一次扩展中，我们只需要求出在这个询问区间内，且在值域内的数的最小值与和，就能成功维护原迭代过程了。

这样就好做了，我们把值域划分为若干区间之后，就能把二维数点简化为区间查询了。

具体实现上，写 \log V 棵线段树，容易维护上述信息。

本题 N,V 同阶，复杂度即为 O(Q \log^2 N)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
const int V=200010,inf=0x3f3f3f3f3f3f3f3f;
int a[201000],lg[201000];
struct Data{
    int x,y;
    Data operator*(const Data &k)const{
        return {x+k.x,min(y,k.y)};
    }
};
struct segtree{
    int sum[801000],Min[801000];
    void init(){
        for(int i=1;i<=n*4;i++) Min[i]=inf;
    }
    void pushup(int p){
        sum[p]=sum[p<<1]+sum[p<<1|1];
        Min[p]=min(Min[p<<1],Min[p<<1|1]);
    }
    void erase(int p,int L,int R,int pos){
        if(L==R) return (void)(Min[p]=inf,sum[p]=0);
        int mid=(L+R)>>1;
        if(pos<=mid) erase(p<<1,L,mid,pos);
        else erase(p<<1|1,mid+1,R,pos);
        pushup(p);
    }
    void update(int p,int L,int R,int pos,int v){
        if(L==R) return (void)(Min[p]=sum[p]=v);
        int mid=(L+R)>>1;
        if(pos<=mid) update(p<<1,L,mid,pos,v);
        else update(p<<1|1,mid+1,R,pos,v);
        pushup(p);
    }
    Data qry(int p,int L,int R,int l,int r){
        if(l<=L&&R<=r) return {sum[p],Min[p]};
        Data res={0,inf};
        int mid=(L+R)>>1;
        if(l<=mid) res=res*qry(p<<1,L,mid,l,r);
        if(r>mid) res=res*qry(p<<1|1,mid+1,R,l,r);
        return res;
    }
}sgt[19];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=V;i++){
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=18;i++){
        sgt[i].init();
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sgt[lg[a[i]]].update(1,1,n,i,a[i]);
    }
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            sgt[lg[a[x]]].erase(1,1,n,x);
            sgt[lg[y]].update(1,1,n,x,y);
            a[x]=y;
        }
        else{
            int now=0;
            for(int i=1;i<=18;i++){
                auto t=sgt[i].qry(1,1,n,x,y);
                if(t.y>now+1) break;
                now+=t.x;
            }
            cout<<now+1<<'\n';
        }
    }
    return 0;
}