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

· · 题解

单点修改，区间查询集合 \{a_l,\cdots,a_r\} 最小不能表示出的正整数是什么。

不带修就是神秘数，考虑这题是如何做的。

我们将 \{a_l,\cdots,a_r\} 从小到大排序，现在是第 i 个数可以表示出所有 [1,now] 中的所有数，如果 a_{i+1} \leq now + 1 那么就可以表示出 [1,a_{i+1}+now] 用主席树优化，每次就等于 [1,now] 中所有数的和，最多执行 O(\log n) 次，那么时间复杂度就是 O(n \log ^2 n) 的，带修就是树套树，做到 O(n \log ^3 n)。

但是可能过不去，考虑神秘数的倍增分块写法，按照 [2^k,2^{k+1}) 分组，那么从小到大枚举每一段，令 x 为这一组的最小值。

那么可以开 \log n 个线段树来分别维护每一段，就变为了区间求最小值与区间求和，单点修改，都是好写的。

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
constexpr ll N=2e5+5,inf=1e18;
ll n,m,a[N],id[N];
struct Tree{
    ll w;
    struct node{
        ll sum,mn;
    }tree[N<<2];
    inline void pushup(node &A,node B,node C){
        A.sum=B.sum+C.sum;
        A.mn=min(B.mn,C.mn);
    }
    void build(int rt,int l,int r){
        if(l==r){
            if((1<<w)<=a[l] && a[l]<(1<<w+1)) tree[rt]={a[l],a[l]};
            else tree[rt]={0,inf};
            return ;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
    }
    void modify(int rt,int l,int r,int x,node t){
        if(l==r){
            tree[rt]=t;
            return ;
        }
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,t);
        else modify(rt<<1|1,mid+1,r,x,t);
        pushup(tree[rt],tree[rt<<1],tree[rt<<1|1]);
    }
    node query(int rt,int l,int r,int ql,int qr){
        if(ql<=l && r<=qr) return tree[rt];
        int mid=l+r>>1;
        node res={0,inf};
        if(ql<=mid) pushup(res,res,query(rt<<1,l,mid,ql,qr));
        if(qr>mid) pushup(res,res,query(rt<<1|1,mid+1,r,ql,qr));
        return res;
    }
}tr[21];
inline ll getid(ll x){ll w=0;while((1<<w)<=x){if((1<<w+1)>x) return w;w++;}}
signed main(){
    ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=19;i++) tr[i].w=i,tr[i].build(1,1,n);
    while(m--){
        ll op,x,y;cin>>op>>x>>y;
        if(op==1){
            tr[getid(a[x])].modify(1,1,n,x,{0,inf});
            tr[getid(y)].modify(1,1,n,x,{y,y});
            a[x]=y;
        }else{
            ll now=0;
            for(int w=0;w<=19;w++){
                Tree::node t=tr[w].query(1,1,n,x,y);
                if(t.mn<=now+1) now+=t.sum;
                else break;
            }
            cout<<now+1<<"\n";
        }
    }
    return 0;
}