浅谈树状数组与主席树：https://www.cnblogs.com/AKMer/p/9946944.html
题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3065
去%了一发hzwer的博客学会的。
替罪羊树套线段树，外层维护位置，内层维护权值。
时间复杂度：(O(nlog^2n))
空间复杂度：(O(nlog^2n))
代码如下：
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const double alpha=0.75;
const int maxn=7e4+5,maxsz=2e7;
char s[5];
int n,m,lstans;
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct Segment_tree {
int tot;
vector<int>rub;
int sum[maxsz],ls[maxsz],rs[maxsz];
int newnode() {
if(rub.empty())return ++tot;
else {
int res=rub.back();rub.pop_back();
return res;
}
}
void change(int p,int l,int r,int pos,int v) {
while(1) {
sum[p]+=v;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid) {
if(!ls[p])ls[p]=newnode();
p=ls[p],r=mid;
}
else {
if(!rs[p])rs[p]=newnode();
p=rs[p],l=mid+1;
}
}
}
void recycle(int u) {
if(!u)return;
rub.push_back(u);
recycle(ls[u]),recycle(rs[u]);
sum[u]=ls[u]=rs[u]=0;
}
}T2;
struct TiZuiYang_tree {
vector<int>num;
int tot,root,cnt;
int son[maxn][2];
vector<int>::iterator it;
int rt[maxn],siz[maxn],tmp[maxn],a[maxn],id[maxn];
int build(int l,int r) {
if(r<l)return 0;
if(l==r) {
int u=id[l];son[u][0]=son[u][1]=0;
rt[u]=T2.newnode(),siz[u]=1;
T2.change(rt[u],0,70000,a[u],1);
return u;
}
int mid=(l+r)>>1,u=id[mid];
rt[u]=T2.newnode();siz[u]=1;
son[u][0]=build(l,mid-1);
son[u][1]=build(mid+1,r);
siz[u]+=siz[son[u][0]]+siz[son[u][1]];
for(int i=l;i<=r;i++)T2.change(rt[u],0,70000,a[id[i]],1);
return u;
}
void find(int u,int l,int r) {
if(l==1&&r==siz[u]) {tmp[++cnt]=rt[u];return;}
int sz=siz[son[u][0]];
if(l<=sz+1&&r>=sz+1)num.push_back(a[u]);
if(r<=sz)find(son[u][0],l,r);
else if(l>sz+1)find(son[u][1],l-sz-1,r-sz-1);
else {
if(l<=sz)find(son[u][0],l,sz);
if(r>sz+1)find(son[u][1],1,r-sz-1);
}
}
int query(int l,int r,int rk) {
num.clear(),cnt=0,find(root,l,r);
int L=0,R=70000;
while(L!=R) {
int res=0,mid=(L+R)>>1;
for(int i=1;i<=cnt;i++)
res+=T2.sum[T2.ls[tmp[i]]];
for(it=num.begin();it!=num.end();it++)
if(*it>=L&&(*it)<=mid)res++;
if(res>=rk) {
for(int i=1;i<=cnt;i++)
tmp[i]=T2.ls[tmp[i]];
R=mid;
}
else {
for(int i=1;i<=cnt;i++)
tmp[i]=T2.rs[tmp[i]];
L=mid+1;rk-=res;
}
}
return L;
}
int change(int u,int pos,int x) {
T2.change(rt[u],0,70000,x,1);
int sz=siz[son[u][0]],res;
if(sz+1==pos) {res=a[u];a[u]=x;}
else if(sz>=pos)res=change(son[u][0],pos,x);
else res=change(son[u][1],pos-sz-1,x);
T2.change(rt[u],0,70000,res,-1);
return res;
}
void insert(int &u,int rk,int v) {
if(!u) {
u=++tot;rt[u]=T2.newnode();
T2.change(rt[u],0,70000,v,1);
siz[u]=1;a[u]=v;return;
}
T2.change(rt[u],0,70000,v,1);
int sz=siz[son[u][0]];siz[u]++;
if(sz>=rk)insert(son[u][0],rk,v);
else insert(son[u][1],rk-sz-1,v);
}
void dfs_rebuild(int u) {
if(!u)return;
dfs_rebuild(son[u][0]);
T2.recycle(rt[u]);
id[++cnt]=u;rt[u]=0;
dfs_rebuild(son[u][1]);
}
void find_rebuild(int &u,int rk) {
if(alpha*siz[u]<max(siz[son[u][0]],siz[son[u][1]])) {
cnt=0;dfs_rebuild(u);u=build(1,cnt);
return;
}
if(siz[son[u][0]]>=rk)find_rebuild(son[u][0],rk);
if(rk>siz[son[u][0]]+1)find_rebuild(son[u][1],rk-siz[son[u][0]]-1);
}
}T1;
int main() {
T1.tot=n=read();
for(int i=1;i<=n;i++)
T1.id[i]=i,T1.a[i]=read();
T1.root=T1.build(1,n);
m=read();
for(int i=1;i<=m;i++) {
scanf("%s",s+1);
if(s[1]=='Q') {
int l=read()^lstans,r=read()^lstans,k=read()^lstans;
lstans=T1.query(l,r,k);printf("%d
",lstans);
}
if(s[1]=='M') {
int pos=read()^lstans,x=read()^lstans;
T1.change(T1.root,pos,x);
}
if(s[1]=='I') {
int pos=read()^lstans,x=read()^lstans;
T1.insert(T1.root,pos-1,x);
T1.find_rebuild(T1.root,pos);
}
}
return 0;
}