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

· · 题解

树套树解法。

sol

考虑每个询问的答案是什么。

就是说 [L,R] 的 k 个数构成的集合，考虑把这个集合的所有子集的元素和放到一个集合 M 里，答案就是这个集合的 \operatorname{mex} 对吧（0 不考虑）。

但是这个 \operatorname{mex} 很难维护出来，原因就是你 k 个数就会有多达 2^k 级别的和，你要维护这个 M 就爆炸了。

换一个角度考虑，我们只需要关注这 k 个数的和能任意取到 [1,S]，则答案就是 S+1。

考虑去做维护 M 的事情，假设当前你的 M 能任意取到 [1,S]。当你 M 里要进来一个 v，考虑 v 满足什么条件能让 [1,S'] 依然是连续的。

显然 v\le S+1 时，v 加进去这个和依然连续，范围 S'=S+v。

那我们从小到大一个一个去加不就行了，这显然是对的，但是复杂度不可接受。

其实发现你一次性把 v\le S+1 的所有 v 都加进去是没毛病的，S'=S+\sum v。

然后可以证明对于一个区间去做这个往 M 里加 v 的操作是 O(\log (\sum a_i)) 次的。

因为上一轮把 \le S_{old}+1 的数全加进去了，这一次加的数肯定是 (S_{old}+1,S] 之间的（如果有数进来），所以 S'\ge S+S_{old}+1， 这个 S 会以斐波那契数列的增长速度增长，然后很快就涨到 \max a_i 了，此时所有数都可以取到了。

分析完一通发现实现是简单的。观察查询实际上就是在做 [L,R] 中值域 [1,S+1] 的数的和，结合修改一个显然的带修二维数点，但是不能离线，原因是你的 S 是不断变化的。

每次查询你就把那个 S\gets S+\sum v，直到你查询的时候发现查到滚木了就结束了，每次查询大约 O(\log n) 次，实测更小。

但是真正上代码的时候你不能这么干，因为树套树查一次会把在 M 里面的数的和也算上，因此实际上是 S\gets \sum v，终止条件是查询的 \sum v = S，说明不再有 v 加入 M 了。

所以总时间是 O(n\log^3 n) 的，跑代码趋近于 O(n\log^2 n)。

然后就是注意树套树要回收废弃节点，要不然你空间就炸完了。

code

const int N = 2e5 + 2 ;
int n,q,a[N] ;
namespace ST {
    int idx,hd ;
    struct st {
        int l,r ;
        ll sum ;
    }t[(int)2e7] ;
    inline int newnode () {
        if (!hd) return ++idx ;
        else {
            re int u = hd ;
            hd = t[u].l,t[u].l = t[u].r = 0 ;
            return u ;
        }
    }
    inline void delnode (fi u) {t[u].l = hd,hd = u ;}
    struct ST {
        #define mid ((l + r) >> 1)
        #define ls(x) (t[(x)].l)
        #define rs(x) (t[(x)].r)
        int rt ;
        inline void update (int &u,fi l,fi r,fi x,fi k) {
            if (!u) u = newnode() ;
            t[u].sum += k ;
            if (l == r) {
                if (!t[u].sum) delnode(u),u = 0 ;
                return ;
            }
            x <= mid ? update(ls(u),l,mid,x,k) : update(rs(u),mid + 1,r,x,k) ; 
            t[u].sum = t[ls(u)].sum + t[rs(u)].sum ;
            if (!t[u].sum) delnode(u),u = 0 ;
        }
        inline ll query (fi u,fi l,fi r,fi L,fi R) {
            if (!u || l > R || L > r || L > R) return 0 ;
            if (L <= l && r <= R) return t[u].sum ;
            re ll res = 0 ;
            if (L <= mid) res += query(ls(u),l,mid,L,R) ;
            if (R > mid) res += query(rs(u),mid + 1,r,L,R) ;
            return res ;
        }
    }bit[N] ;
    #define lb(x) ((x) & -(x))
    inline void insert (int x,fi k,fi p) {
        while (x <= n) bit[x].update(bit[x].rt,1,N,k,p),x += lb(x) ;
    }
    inline ll query (int l,int r,fi L,fi R) {
        re ll res = 0 ;--l ;
        while (l) res -= bit[l].query(bit[l].rt,1,N,L,R),l -= lb(l) ;
        while (r) res += bit[r].query(bit[r].rt,1,N,L,R),r -= lb(r) ;
        return res ;
    }
}
inline void solve () {
    read(n,q) ;
    for (re int i = 1 ; i <= n ; ++i) read(a[i]),ST::insert(i,a[i],a[i]) ;
    while (q--) {
        re int op,x,y,l,r ;
        re ll S = 0,tmp ;
        read(op) ;
        if (op == 1) {
            read(x,y) ;
            ST::insert(x,a[x],-a[x]) ;
            a[x] = y ;
            ST::insert(x,a[x],a[x]) ;
        }
        if (op == 2) {
            read(l,r) ;
            while (1) {
                tmp = ST::query(l,r,1,min(1ll * N,S + 1)) ;
                if (tmp== S) {
                    write(S + 1,endl) ;
                    break ;
                }
                S = tmp ;
            }
        }
    }
}
int main () {
    solve() ;
    return 0 ;
}