带插入区间K小值的题解

Seauy · 2025-01-24 04:52:15 · 题解

目前有的做法是（默认元素个数、操作数、值域同阶）：

重量平衡树/替罪羊树+线段树合并，时间 O(n\log^2 n)，空间 O(n\log^2 n)，常数较大。
定期分裂块状链表，时间 O(n\sqrt{n})，空间 O(n\sqrt n)，常数较小。

其他什么二分+树套树、操作分块或各种分块、分块/平衡树/线段树/树状数组互相套的做法就不仔细列了，要么常数被第二个做法吊打要么理论复杂度被第一个做法吊打。

第一种做法的空间常数较为玄学导致数组大小有些难开（写指针式线段树时空常数双炸），原因是重量平衡树旋转时重构子树的 \log n 的常数有些难估，以及替罪羊树的常数其实是一坨关于平衡系数 \alpha 的式子。拿替罪羊树举例子，如果你把数据下下来，会发现全过程要新建非常多个结点，只能通过重构/删除元素时尽量回收结点降低常数，但并不会降低空间复杂度。

实际上我们采用这种策略：每 \frac{n}{\log n} 次操作就重构整棵替罪羊树，时间上会增加整体重构的开销，一次重构复杂度 O(n\log n) 所以总共是 O(n \log^2 n) 不会使复杂度退化，此时空间就被优化为 O(n \log n)，因为建树需要的空间是 O(n \log n)，而 \frac{n}{\log n} 次操作均摊每次增加 O(\log^2 n) 的空间。

有人可能要问：替罪羊树的均摊是不是不对？n 个元素 m 次操作重构时遍历的结点个数其实是 O((n+m)\log n) 的，令 m=\frac{n}{\log n} 并不能降低复杂度。实际上 n+m 中的 n 是可以去掉的，回顾替罪羊树的均摊分析，由于这题里我只有插入操作，所以初始的势能 \phi_0 就是最低势能，得出重构的总复杂度跟插入的总复杂度成正比。

最终我们得到了时间 O(n\log^2 n) 空间 O(n \log n) 的做法，但时间常数进一步提升了所以不太指望能在当前数据下吊打块状链表，不过空间开销倒是可以一战了，~~可无奈其空间常数也实在太小了，拼尽全力无法战胜~~。

下面给出个参考代码，挺短的，最大的点 1.94s，63.42MB，或许可以继续调参做到更优。

#include<bits/stdc++.h>
using namespace std;

const double alpha=0.955;
const int MAXN=35e3,MAXM=14e4,MAXV=7e4,LOGM=ceil(log(MAXM)/log(1.0/alpha)+1);
const int SIZE=6e6,LIM=5e6;

int Read()
{
    int res=0;char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) res=res*10+c-'0',c=getchar();
    return res;
}
int GetOP()
{
    char c;
    while(!isalpha(c=getchar()));
    if(c=='Q') return 1;
    if(c=='M') return 2;
    return 3;
}
void Print(int x)
{
    if(x<10) {putchar('0'+x);return;}
    int y=x/10;
    Print(y);
    putchar('0'+x-y*10);
}

int sum[SIZE+5],lson[SIZE+5],rson[SIZE+5],tot;

int New(int x) {sum[++tot]=x; return tot;}
int Plus(int now,int L,int R,int x,int v)
{
    int res=New(sum[now]+v);
    if(L==R) {lson[res]=rson[res]=0; return res;}
    int mid=(L+R)>>1;
    if(x<=mid) lson[res]=Plus(lson[now],L,mid,x,v),rson[res]=rson[now];
    else lson[res]=lson[now],rson[res]=Plus(rson[now],mid+1,R,x,v);
    return res;
}
int Merge(int a,int b)
{
    if(!a || !b) return a^b;
    int res=New(sum[a]+sum[b]);
    lson[res]=Merge(lson[a],lson[b]);
    rson[res]=Merge(rson[a],rson[b]);
    return res;
}

int n,q,root,A[MAXM+5],Size[MAXM+5],Lson[MAXM+5],Rson[MAXM+5],rt[MAXM+5],val[MAXM+5],m;

int Q[4*LOGM+5],Tail;
void GetQ(int now,int L,int R)
{
    if(L==1 && R==Size[now]) {Q[++Tail]=rt[now];return;}
    if(L<=Size[Lson[now]]+1 && Size[Lson[now]]+1<=R) Q[++Tail]=val[now];
    if(L<=Size[Lson[now]]) GetQ(Lson[now],L,min(R,Size[Lson[now]]));
    if(Size[Lson[now]]+1<R) GetQ(Rson[now],max(1,L-Size[Lson[now]]-1),R-Size[Lson[now]]-1);
}
int Search(int L,int R,int x)
{
    if(L==R) return L;
    int Lsize=0,mid=(L+R)>>1;
    for(int i=1;i<=Tail;i++) Lsize+=sum[lson[Q[i]]];
    if(x<=Lsize) {for(int i=1;i<=Tail;i++) Q[i]=lson[Q[i]]; return Search(L,mid,x);}
    for(int i=1;i<=Tail;i++) Q[i]=rson[Q[i]]; return Search(mid+1,R,x-Lsize);
}
int Query(int L,int R,int x) {Tail=0,GetQ(root,L,R); return Search(0,MAXV,x);}

int Modify(int now,int x,int v)
{
    if(Size[Lson[now]]+1==x)
    {
        int res=A[now];
        val[now]=Plus(val[now],0,MAXV,A[now],-1),rt[now]=Plus(rt[now],0,MAXV,A[now],-1);
        A[now]=v;
        val[now]=Plus(val[now],0,MAXV,A[now],1),rt[now]=Plus(rt[now],0,MAXV,A[now],1);
        return res;
    }
    int res;
    if(x<=Size[Lson[now]]) res=Modify(Lson[now],x,v);
    else res=Modify(Rson[now],x-Size[Lson[now]]-1,v);
    rt[now]=Plus(rt[now],0,MAXV,res,-1),rt[now]=Plus(rt[now],0,MAXV,v,1);
    return res;
}

int tmp[MAXM+5];
void GetTmp(int now) {if(now) GetTmp(Lson[now]),tmp[++Tail]=now,GetTmp(Rson[now]);}
int Build(int L,int R)
{
    if(L>R) return 0;
    int mid=(L+R)>>1,now=tmp[mid];
    Lson[now]=Build(L,mid-1),Rson[tmp[mid]]=Build(mid+1,R);
    rt[now]=Merge(Merge(rt[Lson[now]],rt[Rson[now]]),val[now]=Plus(0,0,MAXV,A[now],1));
    Size[now]=Size[Lson[now]]+1+Size[Rson[now]];
    return now;
}
void Rebuild(int &now)  {Tail=0,GetTmp(now),now=Build(1,Tail);}
void Insert(int &now,int x,int v)
{
    if(!now) {A[now=++m]=v,rt[now]=val[now]=Plus(0,0,MAXV,v,1),Size[now]=1;return;}
    ++Size[now];
    rt[now]=Plus(rt[now],0,MAXV,v,1);
    if(x<=Size[Lson[now]]+1) Insert(Lson[now],x,v);
    else Insert(Rson[now],x-Size[Lson[now]]-1,v);
    if(alpha*Size[now]<max(Size[Lson[now]],Size[Rson[now]])) Rebuild(now);
}

int main()
{
    n=m=Read();
    for(int i=1;i<=n;i++) A[i]=Read(),tmp[i]=i;
    root=Build(1,n);
    q=Read();
    int cnt=0;
    for(int opt,x,y,lst=0;q--;)
    {
        opt=GetOP(),x=Read()^lst,y=Read()^lst;
             if(opt==1) Print(lst=Query(x,y,Read()^lst)),putchar('\n');
        else if(opt==2) Modify(root,x,y);
        else Insert(root,x,y);
        if(tot>LIM) tot=0,Rebuild(root);
    }
    return 0;
}

UT 给了个常数更小的做法：外层用树状数组维护值域，内层用平衡树维护下标，需要比较两个元素位置的前后关系，用动态标号法（参考可持久化并查集和后缀平衡树）。

带插入区间K小值 的题解

带插入区间K小值的题解