这是在线算法的代码（树状数组套可持久化线段树）

#include<iostream>
#include<cstdio>
using namespace std;
struct node{int ls,rs,sum;}tr[45000004];
int tot=0;
int a[50005],n,rt[50005];
void upd(int &rt,int l,int r,int x,int k){
//	printf("%d %d %d\n",l,r,rt); 
//	if(tot>100*100004)cout<<tot<<endl;
	if(!rt)rt=++tot;
	tr[rt].sum+=k;
	if(l==r){return;}
	int mid=l+r>>1;
	if(x<=mid)upd(tr[rt].ls,l,mid,x,k);
	else upd(tr[rt].rs,mid+1,r,x,k);
}int lowbit(int x){return x&-x;}
void update(int pos,int x,int k){for(int i=pos; i<=n; i+=lowbit(i))upd(rt[i],0,100000000,x,k);}
int que(int rt,int l,int r,int x){
	if(r<=x){return tr[rt].sum;}
	int mid=l+r>>1;
	if(mid>=x){return que(tr[rt].ls,l,mid,x);}
	else {return tr[tr[rt].ls].sum+que(tr[rt].rs,mid+1,r,x);}
}int query(int pos,int x){int ans=0;for(int i=pos; i; i-=lowbit(i))ans+=que(rt[i],0,100000000,x);return ans;}
int find(int rt1[],int rt2[],int cnt1,int cnt2,int l,int r,int k){
	if(l==r){return l;}
	int sum=0;
	for(int i=1; i<=cnt1;i++)sum+=tr[tr[rt1[i]].ls].sum;
	for(int i=1; i<=cnt2;i++)sum-=tr[tr[rt2[i]].ls].sum;
	int mid=l+r>>1; 
	if(sum>=k){
		for(int i=1; i<=cnt1;i++)rt1[i]=tr[rt1[i]].ls;
		for(int i=1; i<=cnt2;i++)rt2[i]=tr[rt2[i]].ls;
		return find(rt1,rt2,cnt1,cnt2,l,mid,k);
	}else{
		for(int i=1; i<=cnt1;i++)rt1[i]=tr[rt1[i]].rs;
		for(int i=1; i<=cnt2;i++)rt2[i]=tr[rt2[i]].rs;
		return find(rt1,rt2,cnt1,cnt2,mid+1,r,k-sum);
	}
}int find_Kth(int l,int r,int k){
	int rt1[505],rt2[505],cnt1=0,cnt2=0;
	for(int i=r; i; i-=lowbit(i))rt1[++cnt1]=rt[i];
	for(int i=l-1;i;i-=lowbit(i))rt2[++cnt2]=rt[i];
//	cout<<rt[cnt1]<<" "<<cnt2<<endl;
	return find(rt1,rt2,cnt1,cnt2,0,100000000,k);
}
int main(){
// 	freopen("P3380_1.in","r",stdin);
// 	freopen("1919810.out","w",stdout); 
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		update(i,a[i],1);
	}while(m--){
		int op,l,r,k;
		scanf("%d%d%d",&op,&l,&r);
		if(op==3){
			update(l,a[l],-1);
			a[l]=r;
			update(l,a[l],1);
		}else{
			scanf("%d",&k);
			if(op==1)printf("%d\n",query(r,k-1)-query(l-1,k-1)+1);
			else if(op==2)printf("%d\n",find_Kth(l,r,k));
			else if(op==4){
				int tmp=query(r,k-1)-query(l-1,k-1);
				if(tmp==0)printf("-2147483647\n");
				else printf("%d\n",find_Kth(l,r,tmp));
			}else{
				int tmp=query(r,k)-query(l-1,k)+1;
				if(tmp>r-l+1)printf("2147483647\n");
				else printf("%d\n",find_Kth(l,r,tmp));
			}
		}
	}
	return 0;
}

这是加上离散化以后的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{int ls,rs,sum;}tr[45000004];
int tot=0;int num[1000005];
int a[50005],n,rt[50005];
void upd(int &rt,int l,int r,int x,int k){
	if(!rt)rt=++tot;
	tr[rt].sum+=k;
	if(l==r){return;}
	int mid=l+r>>1;
	if(x<=mid)upd(tr[rt].ls,l,mid,x,k);
	else upd(tr[rt].rs,mid+1,r,x,k);
}int lowbit(int x){return x&-x;}
void update(int pos,int x,int k){for(int i=pos; i<=n; i+=lowbit(i))upd(rt[i],1,num[0],x,k);}
int que(int rt,int l,int r,int x){
	if(r<=x){return tr[rt].sum;}
	int mid=l+r>>1;
	if(mid>=x){return que(tr[rt].ls,l,mid,x);}
	else {return tr[tr[rt].ls].sum+que(tr[rt].rs,mid+1,r,x);}
}int query(int pos,int x){int ans=0;for(int i=pos; i; i-=lowbit(i))ans+=que(rt[i],1,num[0],x);return ans;}
int find(int rt1[],int rt2[],int cnt1,int cnt2,int l,int r,int k){
	if(l==r){return l;}
	
	int sum=0;
	for(int i=1; i<=cnt1;i++)sum+=tr[tr[rt1[i]].ls].sum;
	for(int i=1; i<=cnt2;i++)sum-=tr[tr[rt2[i]].ls].sum;
	int mid=l+r>>1; 
//	cout<<l<<" "<<r<<" "<<sum<<" "<<k<<endl;
	if(sum>=k){
		for(int i=1; i<=cnt1;i++)rt1[i]=tr[rt1[i]].ls;
		for(int i=1; i<=cnt2;i++)rt2[i]=tr[rt2[i]].ls;
		return find(rt1,rt2,cnt1,cnt2,l,mid,k);
	}else{
		for(int i=1; i<=cnt1;i++)rt1[i]=tr[rt1[i]].rs;
		for(int i=1; i<=cnt2;i++)rt2[i]=tr[rt2[i]].rs;
		return find(rt1,rt2,cnt1,cnt2,mid+1,r,k-sum);
	}
}int find_Kth(int l,int r,int k){
	int rt1[505],rt2[505],cnt1=0,cnt2=0;
	for(int i=r; i; i-=lowbit(i))rt1[++cnt1]=rt[i];
	for(int i=l-1;i;i-=lowbit(i))rt2[++cnt2]=rt[i];
	return find(rt1,rt2,cnt1,cnt2,1,num[0],k);
}
struct que{int op,l,r,k;}b[100005];
int has(int x){return lower_bound(num+1,num+1+num[0],x)-num;}
int main(){
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		num[++num[0]]=a[i];
//		update(i,a[i],1);
	}for(int i=1; i<=m; i++){
		int op,l,r,k;
		scanf("%d%d%d",&op,&l,&r);
		b[i].op=op,b[i].l=l,b[i].r=r;
		if(op!=3){
			scanf("%d",&k);
			b[i].k=k;
			if(op!=2)num[++num[0]]=k;
		}else num[++num[0]]=r;
//		if(op==3){
//			update(l,a[l],-1);
//			a[l]=r;
//			update(l,a[l],1);
//		}else{
//			scanf("%d",&k);
//			if(op==1)printf("%d\n",query(r,k-1)-query(l-1,k-1)+1);
//			else if(op==2)printf("%d\n",find_Kth(l,r,k));
//			else if(op==4){
//				int tmp=query(r,k-1)-query(l-1,k-1);
//				if(tmp==0)printf("-2147483647\n");
//				else printf("%d\n",find_Kth(l,r,tmp));
//			}else{
//				int tmp=query(r,k)-query(l-1,k)+1;
//				if(tmp>r-l+1)printf("2147483647\n");
//				else printf("%d\n",find_Kth(l,r,tmp));
//			}
//		}
	}sort(num+1,num+1+num[0]);
	num[0]=unique(num+1,num+1+num[0])-num-1;
//	cout<<num[0]<<endl;
	for(int i=1; i<=n; i++)a[i]=has(a[i]),update(i,a[i],1);
	for(int i=1; i<=m; i++){
		int op,l,r,k;
		op=b[i].op,l=b[i].l,r=b[i].r;
		if(op==3){
			r=has(r);
			update(l,a[l],-1);
			a[l]=r;
			update(l,a[l],1);
		}else{
			if(op==2){
				k=b[i].k;
//				cout<<l<<" "<<r<<endl;
				printf("%d\n",num[find_Kth(l,r,k)]);
//				cout<<"KTH"<<" "<<find_Kth(l,r,k)<<endl;
			}
			else{
				k=has(b[i].k);
				if(op==1)printf("%d\n",query(r,k-1)-query(l-1,k-1)+1);
				else if(op==4){
					int tmp=query(r,k-1)-query(l-1,k-1);
					if(tmp==0)printf("-2147483647\n");
					else printf("%d\n",num[find_Kth(l,r,tmp)]);
				}else{
					int tmp=query(r,k)-query(l-1,k)+1;
					if(tmp>r-l+1)printf("2147483647\n");
					else printf("%d\n",num[find_Kth(l,r,tmp)]);
				}
			}
		}
	}
	return 0;
}

有无佬哥帮助蒟蒻解释一下，是因为蒟蒻写得太弱了还是因为离散化就是更慢？