前置知识:
普通主席树，树状数组
大概
待修主席树
和静态的一样
只不过还要加一颗树
来维护你修改的值
这棵树就是是树状数组,每个节点上再维护一颗动态开点线段树
(就是所说的树套树，不过没啥可怕的，就是麻烦一丢丢)
查询的时候老样子
不过要多加上树状数组中的值罢了
代码还算好些，如果 主席树，树状数组熟的话
末尾
我知道我说的一定看不懂，因为我一开始找了10几篇博客也没看懂
直到看到他们的博客，真的挺详细的，自己看去吧
博客1
博客2
代码
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=2e5+7;
inline int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,w[maxn],rt[maxn],lsh[maxn];
int js,cnt;
int ch[maxn*50][2],siz[maxn*50];
int a[maxn],b[maxn],mmp;
struct QQQ {
char s;
int a,b,c;
}Q[maxn];
inline int lowbit(int x) {return x&-x;}
void build(int &now,int old,int l,int r,int k) {
//@普通主席树建树，一毛一样好吧
//now在old的基础上把k位置上的个数+gs
now=++cnt;
ch[now][0]=ch[old][0];
ch[now][1]=ch[old][1];
siz[now]=siz[old]+1;
if(l==r) return;
int mid=(l+r)>>1;
if(k<=mid) build(ch[now][0],ch[old][0],l,mid,k);
else build(ch[now][1],ch[old][1],mid+1,r,k);
}
void modify(int &now,int l,int r,int k,int gs) {
if(!now) now=++cnt;
siz[now]+=gs;
if(l==r) return;
int mid=(l+r)>>1;
if(k<=mid) modify(ch[now][0],l,mid,k,gs);
else modify(ch[now][1],mid+1,r,k,gs);
}
int query(int now,int old,int l,int r,int k) {
if(l==r) return l;
int tot=siz[ch[now][0]]-siz[ch[old][0]],mid=(l+r)>>1;
for(int i=1;i<=a[0];++i) tot+=siz[ch[a[i]][0]];//,cout<<i<<" "<<a[i]<<"a
";
for(int i=1;i<=b[0];++i) tot-=siz[ch[b[i]][0]];//,cout<<i<<" "<<b[i]<<"b
";
if(tot>=k) {
for(int i=1;i<=a[0];++i) a[i]=ch[a[i]][0];
for(int i=1;i<=b[0];++i) b[i]=ch[b[i]][0];
return query(ch[now][0],ch[old][0],l,mid,k);
} else {
for(int i=1;i<=a[0];++i) a[i]=ch[a[i]][1];
for(int i=1;i<=b[0];++i) b[i]=ch[b[i]][1];
return query(ch[now][1],ch[old][1],mid+1,r,k-tot);
}
}
int main() {
//read
n=read(),m=read();
FOR(i,1,n) lsh[i]=w[i]=read();
js=n;
char s[100];
FOR(i,1,m) {
scanf("%s",s);
if(s[0]=='Q') {
Q[i].s='Q';
Q[i].a=read();
Q[i].b=read();
Q[i].c=read();
} else {
Q[i].s='C';
Q[i].a=read();
Q[i].b=read();
lsh[++js]=Q[i].b;
}
}
//lsh
sort(lsh+1,lsh+1+js);
js=unique(lsh+1,lsh+1+js)-lsh-1;
FOR(i,1,n)
w[i]=lower_bound(lsh+1,lsh+1+js,w[i])-lsh;
FOR(i,1,m)
if(Q[i].s=='C')
Q[i].b=lower_bound(lsh+1,lsh+1+js,Q[i].b)-lsh;
//init
FOR(i,1,n) build(rt[i],rt[i-1],1,js,w[i]);
FOR(i,1,m) {
if(Q[i].s=='Q') {
a[0]=b[0]=0;
for(int j=Q[i].b;j>=1;j-=lowbit(j)) a[++a[0]]=rt[j+n];//now
for(int j=Q[i].a-1;j>=1;j-=lowbit(j)) b[++b[0]]=rt[j+n];//old
int ans=query(rt[Q[i].b],rt[Q[i].a-1],1,js,Q[i].c);
cout<<lsh[ans]<<"
";
} else {
for(int j=Q[i].a;j<=n;j+=lowbit(j)) {
modify(rt[j+n],1,js,w[Q[i].a],-1);
modify(rt[j+n],1,js,Q[i].b,1);
}
w[Q[i].a]=Q[i].b;
}
}
return 0;
}