线段树套权值线段树 一开始Here

开大数组，变成Here

加O2+开大，变成Here 求调 Code:

#include<iostream>
#define L -1
#define R 1e8+1
#define endl '\n'
using namespace std;
int a[50001];
int n,m;
struct node{
	int lc;
	int rc;
	int w;
}tr[30000001];
int cnt=0;
int build(){tr[++cnt].lc=0,tr[cnt].rc=0,tr[cnt].w=0;return cnt;}
struct segment_tree{
	int root=0;
	void pushup(int k){
		tr[k].w=0;
		if(tr[k].lc) tr[k].w=tr[tr[k].lc].w;
		if(tr[k].rc) tr[k].w+=tr[tr[k].rc].w;
	}
	void add(int k,int l,int r,int x,int p){
		if(l==r){tr[k].w+=p;return ;}
		int mid=(l+r)>>1;
		if(x<=mid){if(!tr[k].lc) tr[k].lc=build(); add(tr[k].lc,l,mid,x,p);}
		else{if(!tr[k].rc) tr[k].rc=build();add(tr[k].rc,mid+1,r,x,p);}
		pushup(k);
	}
	int ask(int k,int l,int r,int ql,int qr){
		if(l>=ql&&r<=qr){return tr[k].w;}
		int ret=0;int mid=(l+r)>>1;
		if(ql<=mid) {if(tr[k].lc)ret+=ask(tr[k].lc,l,mid,ql,qr);};
		if(qr>mid) {if(tr[k].rc)ret+=ask(tr[k].rc,mid+1,r,ql,qr);}; 
		return ret;
	}
	int rank(int k){return ask(root,L,R,L,k-1)+1;}
	int kth(int k,int l,int r,int x){
		if(l==r){return l;}int mid=(l+r)>>1;
		if(x<=tr[tr[k].lc].w) return kth(tr[k].lc,l,mid,x);return kth(tr[k].rc,mid+1,r,x-tr[tr[k].lc].w);
	}
	int pre(int k){return kth(root,L,R,rank(k)-1);}
	int nxt(int k){return kth(root,L,R,rank(k)+ask(root,L,R,k,k));}
	
};
struct Node{
	int lc,rc;
	segment_tree w;
}root,TR[200001];
void BUILD(int k,int l,int r){
	TR[k].w.root=build();
	for(int i=l;i<=r;i++) TR[k].w.add(TR[k].w.root,L,R,a[i],1);
	if(l==r) return;
	int mid=(l+r)>>1;
	BUILD(k<<1,l,mid);
	BUILD(k<<1|1,mid+1,r);
}
void change(int k,int l,int r,int pos,int y){
	TR[k].w.add(TR[k].w.root,L,R,a[pos],-1);
	TR[k].w.add(TR[k].w.root,L,R,y,1);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(pos<=mid) change(k<<1,l,mid,pos,y);
	else change(k<<1|1,mid+1,r,pos,y);
}
int Rnk(int k,int l,int r,int x,int ql,int qr){
	if(l>=ql&&r<=qr) return TR[k].w.rank(x)-1;
	int mid=(l+r)>>1,ret=0;
	if(ql<=mid) ret+=Rnk(k<<1,l,mid,x,ql,qr);
	if(qr>mid) ret+=Rnk(k<<1|1,mid+1,r,x,ql,qr);
	return ret;
}
int rnk(int k,int l,int r,int x,int ql,int qr){
	return Rnk(k,l,r,x,ql,qr)+1;
}
int kth(int x,int ql,int qr){
	int ll=L,rr=R;
	int ans=0;
	while(ll<=rr){
		int mid=(ll+rr)>>1;
		if(rnk(1,1,n,mid,ql,qr)<=x)
			ll=mid+1,ans=mid;
		else rr=mid-1;
	}
	return ans;
}
int pre(int l,int r,int k){if(rnk(1,1,n,k,l,r)==1) return -2147483647;return kth(rnk(1,1,n,k,l,r)-1,l,r);}
int nxt(int l,int r,int k){if(rnk(1,1,n,k,l,r)==r-l+1) return 2147483647;return kth(rnk(1,1,n,k+1,l,r),l,r);}
int main(){
//	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	BUILD(1,1,n);
	for(int i=1;i<=m;i++){
		int opt,l,r,k,pos;
//		cin>>l>>r>>k;
		cin>>opt;
		if(opt==1){
			cin>>l>>r>>k;
			cout<<rnk(1,1,n,k,l,r)<<endl;
		}
		if(opt==2){
			cin>>l>>r>>k;
			cout<<kth(k,l,r)<<endl;
		}
		if(opt==3){
			cin>>pos>>k;
			change(1,1,n,pos,k);
		}
		if(opt==4){
			cin>>l>>r>>k;
			cout<<pre(l,r,k)<<endl;
		}
		if(opt==5){
			cin>>l>>r>>k;
			cout<<nxt(l,r,k)<<endl;
		}
	}
}