- 给定一个长度为\(n\)的序列。
- \(q\)次操作，分为三种：询问区间第\(k\)大、修改一个值、插入一个值。
- \(n\le3.5\times10^4\)，插入操作数\(\le3.5\times10^4\)，修改和查询操作数分别\(\le7\times10^4\)，所有值\(\le7\times10^4\)，强制在线
块状链表
其实我从未写过块状链表，是把这道题当作块状链表板子来做的。
众所周知，数组是一种\(O(n)\)插入\(O(1)\)查询的数据结构，链表是一种\(O(1)\)插入\(O(n)\)查询的数据结构，把它们均衡一下就能得到一个\(O(\sqrt n)\)插入\(O(\sqrt n)\)查询的数据结构。
当然有人会奇怪，为什么不用\(FHQ-Treap\)或\(Splay\)做到\(O(logn)\)插入\(O(logn)\)查询，这就像在问一道分块题目为什么要用分块而不用线段树、平衡树之类的数据结构，肯定是因为好写啊，而且分块可塑性强，也能方便地支持更多操作。
具体地，其实我们就是把每\(\sqrt n\)个元素绑成一个块放到链表上去，可以先在链表上枚举块找到一次插入/查询位置所在的块，然后直接枚举块中的元素找到对应的位置。
插入就是插入，因为块大小是\(O(\sqrt n)\)的直接暴力即可。
但毒瘤出题人可能会拼命往你一个块里猛塞元素卡你，因此还要写个分裂，当一个块大小大于\(2\sqrt n\)，就把这个块分成两个。块内元素直接均分，而在链表上相当于要插入一个新元素，应该是一个非常基础的操作了。
值域分块+前缀和
查询第\(k\)大一个比较好的做法就是值域分块了。
对于这道题，我们给链表上的元素维护一个前缀和，记录\(p_{id,x}\)和\(q_{id,s}\)分别表示到链表上编号为\(id\)的块为止，之前有多少数等于\(x\)，有多少个数在值域块\(s\)中。
询问直接找到左右端点对应的块，散块暴力，整块前缀和差分，先枚举答案在哪个值域块，再枚举答案在值域块中的具体值。
块分裂的时候，发现到分裂出的后一个块的前缀和与原先相同，只要从前一个块的前缀和中减去分到后一个块中的元素即可。
代码：\(O(n\sqrt n)\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 70000
#define SZ 400
using namespace std;
int n,a[N+5],sz,cnt,pre[SZ+5],nxt[SZ+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
I void readc(char& x) {W(isspace(x=tc()));}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
namespace V//值域分块
{
int sz,bl[N+5],p[SZ+5][N+5],q[SZ+5][SZ+5];I void Build() {sz=sqrt(N);for(RI i=0;i<=N;++i) bl[i]=i/sz;}//初始化
I void U(CI id,CI x,CI v) {for(RI i=id;i;i=nxt[i]) p[i][x]+=v,q[i][bl[x]]+=v;}//修改前缀和
I int P(CI L,CI R,CI x) {return p[R][x]-p[L][x];}I int Q(CI L,CI R,CI x) {return q[R][x]-q[L][x];}//差分
}
struct Block
{
int id,n,a[2*SZ+5];I int& operator [] (CI x) {return a[x];}
I void A(CI p,CI v) {for(RI i=++n;i^p;--i) a[i]=a[i-1];a[p]=v,V::U(id,v,1);}//在第p个位置插入一个元素v
I void U(CI p,CI v) {V::U(id,a[p],-1),V::U(id,v,1),a[p]=v;}//修改第p个位置的元素为v
}B[SZ+5];
int bl[N+5];I void Build()//初始化建块状链表
{
RI i;for(sz=sqrt(n),i=1;i<=n;++i) bl[i]=(i-1)/sz+1;cnt=bl[n];//分块
for(i=0;i^bl[n];++i) nxt[i]=i+1;for(i=1;i<=bl[n];++i) pre[i]=i-1,B[i].id=i;//建链表
for(i=1;i<=n;++i) B[bl[i]].A(B[bl[i]].n+1,a[i]);//把元素加到块中
}
I void Split(CI id)//分裂编号为id的块
{
RI i,x;pre[++cnt]=id,pre[nxt[cnt]=nxt[id]]=cnt,nxt[id]=cnt,B[cnt].id=cnt;//新建一个块
for(i=0;i<=N;++i) V::p[cnt][i]=V::p[id][i];for(i=0;i<=V::bl[N];++i) V::q[cnt][i]=V::q[id][i];//继承前缀和
for(i=sz+1;i<=B[id].n;++i) B[cnt][++B[cnt].n]=x=B[id][i],--V::p[id][x],--V::q[id][V::bl[x]];B[id].n=sz;//把左块元素分到右边，删去对左块前缀和贡献
}
I void U(RI x,CI y) {RI i;for(i=nxt[0];B[i].n<x;i=nxt[i]) x-=B[i].n;B[i].U(x,y);}//单点修改
I void A(RI x,CI y)//插入
{
RI i;for(i=nxt[0];B[i].n<x&&i;i=nxt[i]) x-=B[i].n;//找到在哪个块
if(!i) {for(i=nxt[0];nxt[i];i=nxt[i]);x=B[i].n+1;}//特判插在序列最后的元素插在最后一个块
B[i].A(x,y),B[i].n>=2*sz&&(Split(i),0);//如果插入后块大小超过2sz，分裂
}
int pp[N+5],qq[SZ+5];I int Q(RI l,RI r,RI k)//询问区间第k大
{
RI i,j,t;for(i=nxt[0];B[i].n<l;i=nxt[i]) l-=B[i].n,r-=B[i].n;//找左端点所在块
if(r<=B[i].n)//如果在同一个块中
{
for(j=l;j<=r;++j) ++pp[B[i][j]],++qq[V::bl[B[i][j]]];//暴力加入
for(j=0;qq[j]<k;++j) k-=qq[j];for(j*=V::sz;pp[j]<k;++j) k-=pp[j];t=j;//值域分块询问
for(j=l;j<=r;++j) --pp[B[i][j]],--qq[V::bl[B[i][j]]];return t;//撤销，返回答案
}
RI L=i;for(j=l;j<=B[L].n;++j) ++pp[B[L][j]],++qq[V::bl[B[L][j]]];//加入左端点散块
for(;B[i].n<r;i=nxt[i]) r-=B[i].n;RI R=i;for(j=1;j<=r;++j) ++pp[B[R][j]],++qq[V::bl[B[R][j]]];//找到右端点所在块，加入右散块
for(j=0;qq[j]+V::Q(L,pre[R],j)<k;++j) k-=qq[j]+V::Q(L,pre[R],j);//找到在哪个值域块
for(j*=V::sz;pp[j]+V::P(L,pre[R],j)<k;++j) k-=pp[j]+V::P(L,pre[R],j);t=j;//找到值域块中的具体值
for(j=l;j<=B[L].n;++j) --pp[B[L][j]],--qq[V::bl[B[L][j]]];//撤销左散块
for(j=1;j<=r;++j) --pp[B[R][j]],--qq[V::bl[B[R][j]]];return t;//撤销右散块
}
int main()
{
RI i;for(read(n),i=1;i<=n;++i) read(a[i]);V::Build(),Build();
RI Qt,x,y,z,lst=0;char op;read(Qt);W(Qt--) switch(readc(op),read(x,y),op)
{
case 'Q':read(z),writeln(lst=Q(x^lst,y^lst,z^lst));break;
case 'M':U(x^lst,y^lst);break;case 'I':A(x^lst,y^lst);break;
}return clear(),0;
}