【BZOJ3065】带插入区间K小值

题目链接：传送门
题解：
貌似我只会写块链

//by sdfzchy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010,mod=1e9+7;
int n,m;
inline int in()
{
    char tmp=getchar();
    int res=0,f=1;
    while((tmp<'0'||tmp>'9')&&tmp!='-')tmp=getchar();
    if(tmp=='-') f=-1,tmp=getchar();
    while(tmp>='0'&&tmp<='9')   res=(res<<1)+(res<<3)+(tmp^48),tmp=getchar();
    return res*f;
}
int Bo=600;
int la,cnt,a[200][1210],c[200][1210],siz[210],nxt[210];
char s[10];

void change(int pos,int x)
{
    int k=1,p=1;    
    while(pos>siz[k]&&nxt[k]) pos-=siz[k],k=nxt[k];
    int val=a[k][pos];a[k][pos]=x;
    for(p=1;p<=siz[k];p++) if(c[k][p]==val) break; c[k][p]=x;
    for(int i=p-1;i>=1;i--)      if(c[k][i]>c[k][i+1]) swap(c[k][i],c[k][i+1]);
    for(int i=p+1;i<=siz[k];i++) if(c[k][i]<c[k][i-1]) swap(c[k][i],c[k][i-1]);
}

void reset(int x)
{
    ++cnt;
    nxt[cnt]=nxt[x];nxt[x]=cnt;
    siz[cnt]=siz[x]=Bo;
    for(int i=1;i<=Bo;i++) c[x][i]=a[x][i],c[cnt][i]=a[cnt][i]=a[x][i+Bo];
    sort(c[x]+1,c[x]+siz[x]+1);
    sort(c[cnt]+1,c[cnt]+siz[cnt]+1);   
}

void ins(int pos,int x)
{
    int k=1,p=1;
    while(pos>siz[k]&&nxt[k]) pos-=siz[k],k=nxt[k]; siz[k]++;
    for(int i=siz[k];i>pos;i--) a[k][i]=a[k][i-1]; a[k][pos]=x;
    if(siz[k]==2*Bo) reset(k);
    else
    {
        c[k][siz[k]]=x;p=siz[k];
        while(p>1&&c[k][p]<c[k][p-1])
            swap(c[k][p],c[k][p-1]),p--;
    }
}

int ask(int x,int val)
{
    int l=1,r=siz[x],ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(c[x][mid]<val) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}
int query(int l,int r,int k)
{
    int kl=1,kr=1;
    while(l>siz[kl]&&nxt[kl]) l-=siz[kl],kl=nxt[kl];
    while(r>siz[kr]&&nxt[kr]) r-=siz[kr],kr=nxt[kr];
    int ans=0,mid,tot=0,L=0,R=70000;
    while(L<=R)
    {
        tot=0;
        mid=(L+R)>>1;
        if(kl!=kr)
        {
            if(nxt[kl]!=kr) for(int i=nxt[kl];i!=kr;i=nxt[i]) tot+=ask(i,mid);
            for(int i=l;i<=siz[kl];i++) if(a[kl][i]<mid) tot++;
            for(int i=1;i<=r;i++)       if(a[kr][i]<mid) tot++;
        }
        else for(int i=l;i<=r;i++) if(a[kl][i]<mid) tot++;
        if(tot<k) ans=mid,L=mid+1;
        else R=mid-1;
    }
    return ans;
}

void de()
{
        cout<<endl;
        for(int i=1;i;i=nxt[i])
            for(int j=1;j<=siz[i];j++)
            {
                cout<<a[i][j]<<" ";
                if(j==siz[i]) cout<<endl;
            }
        cout<<endl<<endl;
        for(int i=1;i;i=nxt[i])
            for(int j=1;j<=siz[i];j++)
            {
                cout<<c[i][j]<<" ";
                if(j==siz[i]) cout<<endl;
            }
        cout<<endl;
}

int main()
{
    n=in();
    for(int i=1;i<=n;i++) 
    a[(i-1)/Bo+1][(i-1)%Bo+1]=c[(i-1)/Bo+1][(i-1)%Bo+1]=in();
    cnt=(n-1)/Bo+1;
    for(int i=1;i<cnt;i++) siz[i]=Bo,nxt[i]=i+1;
    siz[cnt]=n-(cnt-1)*Bo;
    for(int i=1;i<=cnt;i++) sort(c[i]+1,c[i]+siz[i]+1);
    m=in();
    for(int i=1,l,r;i<=m;i++)
    {
        scanf("%s",s);
        l=in()^la,r=in()^la;
        if(s[0]=='Q') printf("%d\n",la=query(l,r,in()^la));
        else if(s[0]=='M') change(l,r);
        else ins(l,r);
    }
    return 0;
}