我写的是线段树套动态开点权值线段树。

#include<bits/stdc++.h>
using namespace std;
const int N = 50005,inf = 2147483647;
struct T{
	int l,r,mid,rid;	
}t[8*N];
struct iT{
	int ls,rs;
	unsigned short sum;
}it[605*N];
int tot,a[N],lsa[2*N];
//int iq[N],iqt;
int cr(){
	int p = ++tot;
//	if(iqt)p = iq[iqt--];
//	else p = ++tot;
	it[p].ls = it[p].rs = it[p].sum = 0;
	return p;
}
void udi(int p){
	it[p].sum = it[it[p].ls].sum+it[it[p].rs].sum;
}
void cgi(int &p,int to,int l,int r,int k){
	if(!p)p = cr();
	if(l==r){
		it[p].sum+=k;
		//if(!it[p].sum)iq[++iqt] = p,p = 0;
		return;
	}
	int mid = (l+r)>>1;
	if(to<=mid)cgi(it[p].ls,to,l,mid,k);
	else cgi(it[p].rs,to,mid+1,r,k);
	udi(p);
	//if(!it[p].sum)iq[++iqt] = p,p = 0;
}
void build(int p,int l,int r){
	t[p].l = l;t[p].r = r;t[p].mid = (l+r)>>1;
	t[p].rid = 0;
	for(int i = l;i<=r;i++)cgi(t[p].rid,a[i],1,2*N,1);
	if(l==r)return;
	build(p<<1,l,t[p].mid);
	build((p<<1)|1,t[p].mid+1,r);
}
void cgo(int p,int to,int k){
	cgi(t[p].rid,a[to],1,2*N,-1);
	cgi(t[p].rid,k,1,2*N,1);
	if(t[p].l==t[p].r){
		a[t[p].l] = k;
		return;
	}
	if(to<=t[p].mid)cgo(p<<1,to,k);
	else cgo((p<<1)|1,to,k);
}
int n,m,ct;
struct Q{
	int op,l,r,k;
}q[N];
int rs(int a){
	return lower_bound(lsa+1,lsa+ct+1,a)-lsa;
}
int que[N],qt; 
void split(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r){
		que[++qt] = p;
		return;
	}
	if(t[p].mid>=l)split(p<<1,l,r);
	if(t[p].mid<r)split((p<<1)|1,l,r);
}
//here
int qri(int p,int l,int r,int L,int R){
	//here
	//MLE on 10:if(L<=l&&r<=R)return it[p].sum;
	if(L<=l&&r<=R||!p)return it[p].sum;
	int mid = (l+r)>>1,ans = 0;
	if(mid>=L)ans+=qri(it[p].ls,l,mid,L,R);
	if(mid<R)ans+=qri(it[p].rs,mid+1,r,L,R);
	return ans;	
}
int qrk(int x){
	int ans = 1;
	for(int i = 1;i<=qt;i++)ans+=qri(t[que[i]].rid,1,2*N,1,x-1);
	return ans;
}
int nl,nr,nmid,na,nrt[N];
int qrx(int k){
	nl = 1,nr = 2*N,nmid;
	for(int i = 1;i<=qt;i++)nrt[i] = t[que[i]].rid;
	while(nl<nr){
		nmid = (nl+nr)>>1;
		na = 0;
		for(int i = 1;i<=qt;i++)na+=it[it[nrt[i]].ls].sum;
		if(na>=k){
			nr = nmid;
			for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].ls;
		}else{
			k-=na;
			nl = nmid+1;
			for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].rs;
		}
	}
	return lsa[nl];
}
void fd(int l,int r,int x,int op){
	if(nr)return;
	if((r<=x&&op)||(l>=x&&!op)){
		bool fg = 0;
		for(int i = 1;i<=qt;i++)fg|=it[nrt[i]].sum;
		if(!fg)return;
		nr = r;
		nl = l;
		return;
	}
	int mid = (l+r)>>1;
	vector<int> yr;
	for(int i = 1;i<=qt;i++)yr.push_back(nrt[i]);
	if(op){
		if(mid<x){
			for(int i = 1;i<=qt;i++)nrt[i] = it[yr[i-1]].rs;
			fd(mid+1,r,x,op);
		}
		if(!nr){
			for(int i = 1;i<=qt;i++)nrt[i] = it[yr[i-1]].ls;
			fd(l,mid,x,op);
		}
	}else{
		if(mid>=x){
			for(int i = 1;i<=qt;i++)nrt[i] = it[yr[i-1]].ls;
			fd(l,mid,x,op);
		}
		if(!nr){
			for(int i = 1;i<=qt;i++)nrt[i] = it[yr[i-1]].rs;
			fd(mid+1,r,x,op);
		}
	}
}
int qrqh(int x,int op){
	for(int i = 1;i<=qt;i++)nrt[i] = t[que[i]].rid;
	nl = nr = 0;
	if(op)x--;
	else x++;
	fd(1,2*N,x,op);
	if(!nr){
		if(op)return -inf;
		else return inf;
	}
	bool fg;
	while(nl<nr){
		nmid = (nl+nr)>>1;
		fg = 0; 
		if(op){
			for(int i = 1;i<=qt;i++)fg|=it[it[nrt[i]].rs].sum;
			if(fg){
				for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].rs;
				nl = nmid+1;
			}else{
				for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].ls;
				nr = nmid;
			}
		}else{
			for(int i = 1;i<=qt;i++)fg|=it[it[nrt[i]].ls].sum;
			if(fg){
				for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].ls;
				nr = nmid;
			}else{
				for(int i = 1;i<=qt;i++)nrt[i] = it[nrt[i]].rs;
				nl = nmid+1;
			}
		}
	}
	return lsa[nl];
}
int main(){
	it[0].sum = it[0].ls = it[0].rs = 0;
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=n;i++){
		scanf("%d",&a[i]);
		lsa[++ct] = a[i];
	}
	for(int i = 1;i<=m;i++){
		scanf("%d%d%d",&q[i].op,&q[i].l,&q[i].r);
		if(q[i].op!=3){
			scanf("%d",&q[i].k);
			lsa[++ct] = q[i].k;
		}else lsa[++ct] = q[i].r;
	}
	sort(lsa+1,lsa+ct+1);
	ct = unique(lsa+1,lsa+ct+1)-lsa-1;
	for(int i = 1;i<=n;i++)a[i] = rs(a[i]);
	build(1,1,n);
	for(int i = 1;i<=m;i++){
		int op = q[i].op;
		if(op!=3){
			qt = 0;
			split(1,q[i].l,q[i].r);
		}
		if(op<2||op>3)q[i].k = rs(q[i].k);
		if(op==1){
			printf("%d\n",qrk(q[i].k));
		}else if(op==2){
			printf("%d\n",qrx(q[i].k));
		}else if(op==3){
			cgo(1,q[i].l,rs(q[i].r));
		}else if(op==4){
			printf("%d\n",qrqh(q[i].k,1));
		}else printf("%d\n",qrqh(q[i].k,0));
	}
	return 0;
}

对于第76行(qri函数中)，写注释里的会MLE在#10

写没有注释掉的，#10 回收节点100MB左右，不回收180MB左右。为什么会这样？对于动态开点线段树，我在函数的参数中记录线段树节点的左右端点，感觉这样即使在p=0时不返回也不会出什么大问题，为什么改一下空间差别那么大