题意

\(n\) 个数，\(m\) 个操作，每次操作修改某个数，或者询问某个区间的第 \(K\) 小值。

\(1 \leq n \leq 50000\)

\(1 \leq m \leq 10000\)

思路

动态区间第 \(K\) 小的模板题。回到主席树的职能，它维护了一排前缀线段树，假如我们要快速求一段区间的总和，显然优先考虑前缀和；然而如果带上修改，就要考虑树状数组了。这里也相同，我们只需用树状数组套主席树即可，\(x\) 号主席树维护的不再是 \([1,x]\) 的信息，而是 \([x-\text{lowbit(x)}+1,x]\) 的信息。

修改时，像树状数组的修改一样不断加 \(\text{lowbit}\) ，修改 \(\log\) 棵主席树。

查询时，像树状数组一样不断减 \(\text{lowbit}\) ，查询 \(2\log\) 棵主席树。这里可以传入两个 \(\text{vector}\) ，一个加、一个减，然后就可以轻松求出区间第 \(K\) 值了。

总复杂度 \((n+m)\log^2n\) ，然而过不了。

这道题比较卡常，初始的序列应该再用一棵静态主席树解决，动态主席树只存修改的信息，查询时额外加入静态主席树上要加的位置和要减的位置即可。

总复杂度 \(m\log^2n\) ，现在可以过了。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=5e4+5;

const int M=1e4+5;

const int NN=2e6+5;

struct ChairmanTree

{

	int lson[NN],rson[NN],cnt[NN];

	int rt[N+N],tot;

	int &operator [](const int x){return rt[x];}

	void build()

	{

		memset(rt,0,sizeof(rt));

		cnt[tot=0]=0,lson[0]=rson[0]=0;

	}

	void create(int &k){cnt[++tot]=cnt[k],lson[tot]=lson[k],rson[tot]=rson[k],k=tot;}

	void update(int &k,int x,int val,int l,int r)

	{

		create(k);

		if(l==r)

		{

			cnt[k]+=val;

			return;

		}

		int mid=(l+r)>>1;

		if(x<=mid)update(lson[k],x,val,l,mid);

		else update(rson[k],x,val,mid+1,r);

		cnt[k]=cnt[lson[k]]+cnt[rson[k]];

	}

	int query(vector<int>&A,vector<int>&B,int K,int l,int r)

	{

		if(l==r)return l;

		int mid=(l+r)>>1,Cnt=0;

		FOR(i,0,(int)A.size()-1)Cnt+=cnt[lson[A[i]]];

		FOR(i,0,(int)B.size()-1)Cnt-=cnt[lson[B[i]]];

		if(Cnt>=K)

		{

			FOR(i,0,(int)A.size()-1)A[i]=lson[A[i]];

			FOR(i,0,(int)B.size()-1)B[i]=lson[B[i]];

			return query(A,B,K,l,mid);

		}

		else

		{

			FOR(i,0,(int)A.size()-1)A[i]=rson[A[i]];

			FOR(i,0,(int)B.size()-1)B[i]=rson[B[i]];

			return query(A,B,K-Cnt,mid+1,r);

		}

	}

}CT;

int a[N],L[M],R[M],K[M],disc[N+M];

int n,m,tot;

#define lowbit(x) ((x)&-(x))

void update(int k,int val)

{

	int _val=a[k];

	a[k]=val;

	for(;k<=n;k+=lowbit(k))

	{

		CT.update(CT[k],_val,-1,1,tot);

		CT.update(CT[k],val,1,1,tot);

	}

}

int query(int l,int r,int k)

{

	vector<int>A,B;

	A.clear(),B.clear();

	A.push_back(CT[N+r]),B.push_back(CT[N+l-1]);

	for(;r>0;r^=lowbit(r))A.push_back(CT[r]);

	for(l--;l>0;l^=lowbit(l))B.push_back(CT[l]);

	return CT.query(A,B,k,1,tot);

}

#undef lowbit

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		CT.build();

		tot=0;

		scanf("%d%d",&n,&m);

		FOR(i,1,n)scanf("%d",&a[i]),disc[++tot]=a[i];

		FOR(i,1,m)

		{

			char str[5];

			scanf("%s",str);

			if(str[0]=='Q')scanf("%d%d%d",&L[i],&R[i],&K[i]);

			else scanf("%d%d",&L[i],&R[i]),K[i]=-1,disc[++tot]=R[i];

		}

		sort(disc+1,disc+1+tot);

		tot=unique(disc+1,disc+1+tot)-disc-1;

		FOR(i,1,n)a[i]=lower_bound(disc+1,disc+1+tot,a[i])-disc;

		FOR(i,1,m)if(K[i]==-1)R[i]=lower_bound(disc+1,disc+1+tot,R[i])-disc;

		FOR(i,1,n)CT.update(CT[N+i]=CT[N+i-1],a[i],1,1,tot);

		FOR(i,1,m)

		{

			if(K[i]!=-1)printf("%d\n",disc[query(L[i],R[i],K[i])]);

			else update(L[i],R[i]);

		}

	}

	return 0;

}