P4278 带插入区间K小值 记录

· · 个人记录

原来考后才是最好颓废的时候

题意：让你维护一个序列，支持区间询问第 K 小，单点修改，在某个数前插入一个数。

你发现这个数据范围很小，于是你可以随意地整一个 O(n\sqrt n\text{polylog } n) 的算法。

于是还是传统艺能地块状链表，你先分块，分成 B 块，然后插入就适当地自动分裂。

然后你每个块都记录一个排序好的结果，动态维护这个东西。

然后每次你询问一个区间的时候就二分判定一个数是否是第 K 小。

判定时就把散块的数处理掉，整块的东西再用二分掏出来即可。

复杂度 O(n\sqrt n\log n\log V)，V 代表值域。

#define maxn 70010
#define B 1024
int n,m;
int a[B][B*2],b[B][B*2];
int lst,l,r,x,k;
char ch[2];
int nxt[B];
const int blo=512;
int pos[maxn],L[B],R[B],tot,siz[B];
int ask(int l,int r,int k){
  int p=1,q=1;
  while(siz[p]<l)l-=siz[p],p=nxt[p];
  while(siz[q]<r)r-=siz[q],q=nxt[q];
  int tl=0,tr=70000,mid;
  while(tl<=tr){
    mid=(tl+tr)>>1;
    int t=0;
    if(p==q)rep(i,l,r)t+=a[p][i]<mid;
    else{
      rep(i,l,siz[p])t+=a[p][i]<mid;
      rep(i,1,r)t+=a[q][i]<mid;
      int pos=nxt[p];
      while(pos!=q){
        t+=lower_bound(b[pos]+1,b[pos]+siz[pos]+1,mid)-b[pos]-1;
        pos=nxt[pos];
      }
    }
    if(t<k)tl=mid+1;
    else tr=mid-1;
  }
  return tr;
}
void change(int x,int y){
  int p=1,k;
  while(siz[p]<x)x-=siz[p],p=nxt[p];
  rep(i,1,siz[p])if(b[p][i]==a[p][x]){
    k=i;
    break;
  }
  b[p][k]=a[p][x]=y;
  while(k>1&&b[p][k]<b[p][k-1])swap(b[p][k],b[p][k-1]),k--;
  while(k<siz[p]&&b[p][k]>b[p][k+1])swap(b[p][k],b[p][k+1]),k++;
}
void make(int x){
  rep(i,1,siz[x])b[x][i]=a[x][i];
  sort(b[x]+1,b[x]+siz[x]+1);
}
void insert(int x,int y){
  x--;
  int p=1;
  while(siz[p]<x)x-=siz[p],p=nxt[p];
  per(i,siz[p],x+1)a[p][i+1]=a[p][i];
  siz[p]++;
  a[p][x+1]=y;
  b[p][siz[p]]=y;
  if(siz[p]==2*blo){
    nxt[++tot]=nxt[p];
    nxt[p]=tot;
    rep(i,1,blo)a[tot][i]=a[p][i+blo];
    siz[p]=siz[tot]=blo;
    make(p),make(tot);
  }else{
    int k=siz[p];
    while(k>1&&b[p][k]<b[p][k-1])swap(b[p][k],b[p][k-1]),k--;
  }
}
signed main(){
  cin>>n;
  tot=n>>9;
  if(n&511)tot++;
  rep(i,1,tot){
    L[i]=R[i-1]+1;
    R[i]=L[i]+blo-1;
  }R[tot]=n;
  rep(i,1,tot){
    siz[i]=R[i]-L[i]+1;
    rep(j,L[i],R[i])
    cin>>a[i][j-L[i]+1],pos[j]=i;
    if(i<tot)nxt[i]=i+1;
    make(i);
  }
  cin>>m;
  while(m--){
    cin>>ch;
    cin>>l>>r;l^=lst,r^=lst;
    if(ch[0]=='Q'){
      cin>>k,k^=lst;
      cout<<(lst=ask(l,r,k))<<endl;
    }
    if(ch[0]=='M')change(l,r);
    if(ch[0]=='I')insert(l,r);
  }
}