给出一个数组，请你支持单点修改或询问区间第k小。
先离散化。
然后对线段树的每个节点维护一颗权值线段树。
权值线段树内存放区间内的所有点。
然后单点修改操作就是先把对应树链上的a_x全删了，然后把a_x改成y，再插入。
询问第k小就是先dfs出与这个区间有关的线段树节点。
然后在这些节点对应的权值线段树上找第k小。
时间复杂度O(nlognlogn)/
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int M=maxn*256;
int c[M],lson[M],rson[M],tot;
int T[maxn<<2];
int a[maxn],t[maxn],n,q,m;
int up (int u,int l,int r,int p,int v) {
int newRoot=u;
if (!newRoot) newRoot=++tot;
if (l==r) {
c[newRoot]+=v;
return newRoot;
}
int mid=(l+r)>>1;
if (p<=mid) {
lson[newRoot]=up(lson[newRoot],l,mid,p,v);
}
else {
rson[newRoot]=up(rson[newRoot],mid+1,r,p,v);
}
c[newRoot]=c[lson[newRoot]]+c[rson[newRoot]];
return newRoot;
}
void build (int i,int l,int r) {
for (int j=l;j<=r;j++) {
T[i]=up(T[i],1,m,a[j],1);
}
if (l==r) return;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
void Up (int i,int l,int r,int p,int x,int y) {
//外层修改
T[i]=up(T[i],1,m,x,y);
if (l==r) return;
int mid=(l+r)>>1;
if (p<=mid) Up(i<<1,l,mid,p,x,y);
if (p>mid) Up(i<<1|1,mid+1,r,p,x,y);
}
int S[maxn],SS[maxn];//存储查询时的临时根节点
int tol;
void query (int i,int l,int r,int L,int R) {
//有多少个子树需要被查询
if (l>=L&&r<=R) {
S[++tol]=T[i];
return;
}
int mid=(l+r)>>1;
if (L<=mid) query(i<<1,l,mid,L,R);
if (R>mid) query(i<<1|1,mid+1,r,L,R);
}
int kth (int i,int l,int r,int k) {
if (l==r) return l;
int mid=(l+r)>>1;
int sum=0;
for (int j=1;j<=tol;j++) SS[j]=S[j],sum+=c[lson[S[j]]];
if (sum>=k) {
for (int j=1;j<=tol;j++) S[j]=lson[S[j]];
int x=kth(i,l,mid,k);
for (int j=1;j<=tol;j++) S[j]=SS[j];
return x;
}
else {
for (int j=1;j<=tol;j++) S[j]=rson[S[j]];
int x=kth(i,mid+1,r,k-sum);
for (int j=1;j<=tol;j++) S[j]=SS[j];
return x;
}
}
struct que {
int l,r,k,x,y,op;
}Q[maxn];
int cc;
int main () {
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++) scanf("%d",a+i),t[i]=a[i];
cc=n;
for (int i=1;i<=q;i++) {
char op;
//getchar();
cin>>op;
if (op=='Q') {
Q[i].op=1;
scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].k);
}
else {
Q[i].op=2;
scanf("%d%d",&Q[i].x,&Q[i].y);
t[++cc]=Q[i].y;
}
}
sort(t+1,t+cc+1);
m=unique(t+1,t+cc+1)-t-1;
for (int i=1;i<=n;i++) a[i]=upper_bound(t+1,t+m+1,a[i])-t-1;
build(1,1,n);
for (int i=1;i<=q;i++) {
if (Q[i].op==2) {
Q[i].y=upper_bound(t+1,t+m+1,Q[i].y)-t-1;
Up(1,1,n,Q[i].x,a[Q[i].x],-1);
a[Q[i].x]=Q[i].y;
Up(1,1,n,Q[i].x,a[Q[i].x],1);
}
else {
tol=0;
query(1,1,n,Q[i].l,Q[i].r);
int ans=kth(1,1,m,Q[i].k);
printf("%d
",t[ans]);
}
}
}