题解：P4278 带插入区间K小值

· · 题解

前言

不会块状链表……

做法

既然不会块状链表，我们可以操作分块。

设块长是 L，那么每 L 次修改重构出当前 a 数组。

查询 [l,r] 时先倒推出其对应在这个操作分块开始时的 a 上的区间 [l',r']，计算这个操作分块内的修改对它的贡献加上 [l',r']的贡献。

具体的：

总共有 O(L) 个贡献加上 a_{l'}\sim a_{r'} 的贡献。

如何维护 O(L) 个贡献？把它们加入权值线段树就能线段树上二分了。

至于 a_{l'}\sim a_{r'} 重构时主席树即可。

查询在这两棵树上多树二分。

这时候还漏了一件事：重构需要知道现在的 a 序列，需要数据结构支持：插入，修改，遍历。用平衡树即可（当然可以偷懒直接 vector.insert）。

分析复杂度（假设 n,m 同阶）：

查询 O(nL\log V)，重构 O(\dfrac{n^2}{L}\log V)，取 L=\sqrt n，复杂度 O(n\sqrt n \log V)。

但是实际上 m 高达 2.1\times10^5，跑 m\sqrt n \log V 根本过不去。

我们发现查询算贡献部分是 O(n\sqrt n\log V)，多树二分却是 O(n\log V) 的，想办法平衡一下常数。

注意到二分的是一个前缀，那么我们想到用权值树状数组。

但是原本的主席树怎么办，可持久化树状数组（要么开 map 要么动态开点）和主席树吗没有两样。

我们可以序列分块，每个块开一个权值树状数组，设块长为 B，这样 a_{l'}\sim a_{r'} 的贡献就是 O(\dfrac{n}{B}) 个整块权值树状数组加上 O(B) 个散块权值。

把这 O(B) 个散块权值加入刚刚的维护操作分块贡献的权值树状数组内，然后在 O(\dfrac{n}{B}) 个整块和这个权值树状数组上多树二分。

树状数组上二分（其实类似于倍增）：

树状数组的性质：节点 tr_i 维护 (i-\operatorname{lowbit}(i),i] 的区间。

查询最大前缀 x 使 1\sim x 权值和 <k（答案为 x+1，即最小的前缀权值和 \ge k）

设当前答案为 res，当前和为 sum（初值都为 0）。

从 \log V 到 0 枚举二进制位 i，若 sum+tr_{res+2^i}\le k，则 sum\gets sum+tr_{res+2^i},res\gets res+2^i，因为 tr_{res+2^i} 维护的是区间 (res,res+2^i]。

最终复杂度：

操作分块散块 O(nL\log V)，重构 O(\dfrac{n^2}{L}\log V)，序列分块查询 O(nB\log V)+O(\dfrac{n^2}{B}\log V)，取 L=\sqrt n,B=\sqrt n，时间复杂度 O(n\sqrt n\log V)，但是树状数组常数小了。

空间复杂度：序列分块每块一个树状数组 O(n\sqrt n)。

Code

const int MAXN=7e4+10;
const int N=7e4;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,q,ans=0;
const int B=256;
const int MAXB=(N/B)+5;
const int V=7e4;
const int LIM=1024;
const int MAXM=LIM+5;
namespace BIT{
    int tr[MAXB][MAXN];
    #define lowbit(x) x&-x
    int cnt=0;
    int mdf[(MAXM+B)<<1];
    inline void clear_pos(int pos,int x){
        if(!pos){
            tr[x][0]=0;
            return ;
        }
        for(int i=pos;i<=V;i+=lowbit(i))
        {
            if(!tr[x][i]){
                return ;
            }
            tr[x][i]=0;
        }
    }
    inline void clear(){
        for(int i=1;i<=cnt;i++)
        {
            BIT::clear_pos(mdf[i],0);
        }
        cnt=0;
    }
    inline void modify(int pos,int val,int x){
        if(!x){
            cnt++;
            mdf[cnt]=pos;
        }
        if(!pos){
            tr[x][0]+=val;
            return ;
        }
        for(int i=pos;i<=V;i+=lowbit(i))
        {
            tr[x][i]+=val;
        }
    }
    inline int query_pos(int l,int r,int pos,int k){
        int res=tr[0][pos];
        for(int i=l;i<=r;i++)
        {
            res+=tr[i][pos];
            if(res>=k){[[unlikely]]
                return res;
            }
        }
        return res;
    }
    inline int query(int l,int r,int k){
        int res=0,now=query_pos(l,r,0,k);
        if(k<=now){
            return 0;
        }
        k-=now;
        for(int i=16;~i;i--)
        {
            int to=res|(1<<i);
            if(to>V){
                continue;
            }
            now=query_pos(l,r,to,k);
            if(now<k){
                k-=now;
                res=to;
            }
        }
        return res+1;
    }
}
basic_string <int> arr;
int a[MAXN];
int idx[MAXN];
inline void build(){
    int l=0,r=0;
    for(int i=1;i<=m;i++)
    {
        l=r+1;
        r=min(l+B-1,n);
        for(int j=l;j<=r;j++)
        {
            BIT::clear_pos(a[j],i);
        }
    }
    n=arr.size();
    for(int i=1;i<=n;i++)
    {
        a[i]=arr[i-1];
    }
    m=(n+B-1)/B;
    l=0;
    r=0;
    for(int i=1;i<=m;i++)
    {
        l=r+1;
        r=min(l+B-1,n);
        for(int j=l;j<=r;j++)
        {
            idx[j]=i;
            BIT::modify(a[j],1,i);
        }
    }
}
int cnt=0;
bool typ[MAXM];
int pos[MAXM],val[MAXM],lst[MAXM];
inline int query(int l,int r,int k){
    BIT::clear();
    for(int i=cnt;i;i--)
    {
        if(!typ[i]){
            if(l<=pos[i]&&pos[i]<=r){
                BIT::modify(lst[i],-1,0);
                BIT::modify(val[i],1,0);
            }
        }
        else{
            if(l<=pos[i]&&pos[i]<=r){
                BIT::modify(val[i],1,0);
            }
            (l>pos[i])&&(l--);
            (r>=pos[i])&&(r--);
        }
    }
    if(l<=r){
        if(idx[l]==idx[r]){
            for(int i=l;i<=r;i++)
            {
                BIT::modify(a[i],1,0);
            }
        }
        else{
            for(int i=l;idx[i]==idx[l];i++)
            {
                BIT::modify(a[i],1,0);
            }
            for(int i=r;idx[i]==idx[r];i--)
            {
                BIT::modify(a[i],1,0);
            }
        }
        return BIT::query(idx[l]+1,idx[r]-1,k);
    }
    return BIT::query(1,0,k);
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)
    {
        arr.push_back(read());
    }
    build();
    q=read();
    for(int i=1;i<=q;i++)
    {
        char opt=getchar();
        while(opt^'Q'&&opt^'M'&&opt^'I')
        {
            opt=getchar();
        }
        if(opt=='Q'){
            int l=read()^ans,r=read()^ans,k=read()^ans;
            ans=query(l,r,k);
            printf("%d\n",ans);
        }
        if(opt=='M'){
            int p=read()^ans,v=read()^ans;
            cnt++;
            pos[cnt]=p;
            lst[cnt]=arr[p-1];
            val[cnt]=v;
            typ[cnt]=false;
            arr[p-1]=v;
        }
        if(opt=='I'){
            int p=read()^ans,v=read()^ans;
            cnt++;
            pos[cnt]=p;
            val[cnt]=v;
            typ[cnt]=true;
            arr.insert(arr.begin()+p-1,v);
        }
        if(cnt==LIM){
            cnt=0;
            build();
        }
    }
    return 0;
}