FHQ平衡树T了两个求调

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int inf=2147483647;
int m,n,cnt,a[50001];
struct node{
	int val,key,l,r,size;
}t[40000001];
struct tree{
	int l,r,root;
}tr[200001];
int newnode(int val) {
	t[++cnt].val=val;
	t[cnt].size=1;
	t[cnt].key=rand();
	return cnt;
}
void push(int x){t[x].size=1+t[t[x].l].size+t[t[x].r].size;}
void sq(int &x,int &y,int k,int p){
	if(!p){
		x=y=0;
		return ;
	}
	if(t[p].val<=k){
		x=p;
		sq(t[p].r,y,k,t[p].r);
	}
	else{
		y=p;
		sq(x,t[p].l,k,t[p].l);
	}
	push(p);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(t[x].key>t[y].key){
		t[x].r=merge(t[x].r,y);
		push(x);
		return x;
	}
	else {
		t[y].l=merge(x,t[y].l);
		push(y);
		return y;
	}
}
void insert(int val,int &root){
	int x,y;
	sq(x,y,val,root);
	root=merge(merge(x,newnode(val)),y);
}
void del(int val,int &root){
	int x,y,z;
	sq(x,z,val,root);
	sq(x,y,val-1,x);
	root=merge(merge(x,t[y].l),merge(t[y].r,z));
}
int find_pre(int &root,int k){
	int x,y,z,ans;
	sq(x,y,k-1,root),z=x;
	while(z)ans=t[z].val,z=t[z].r;
	root=merge(x,y);
	return ans;
}
int find_back(int &root,int k){
	int x,y,z,ans;
	sq(x,y,k,root),z=y;
	while(z)ans=t[z].val,z=t[z].l;
	root=merge(x,y);
	return ans;
}
int find_rank(int &root,int k){
	int x,y,ans;
	sq(x,y,k,root);
	ans=t[x].size-1;
	root=merge(x,y);
	return ans;
}
void build(int l,int r,int x){
	insert(inf,tr[x].root),insert(-inf,tr[x].root);
	tr[x].l=l;tr[x].r=r;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(l,mid,x*2);build(mid+1,r,x*2+1);
}
void change(int p,int x,int kk,int k){
	del(kk,tr[x].root),insert(k,tr[x].root);
	if(tr[x].l==tr[x].r)return ;
	int mid=(tr[x].l+tr[x].r)/2;
	if(p<=mid)change(p,x*2,kk,k);
	else change(p,x*2+1,kk,k);
}
void seg_insert(int x,int p,int k){
	insert(k,tr[x].root);
	if(tr[x].l==tr[x].r)return ;
	int mid=(tr[x].l+tr[x].r)/2;
	if(p<=mid)seg_insert(x*2,p,k);
	else seg_insert(x*2+1,p,k);
}
int ask_pre(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r)return find_pre(tr[x].root,k);
	int mid=(tr[x].l+tr[x].r)/2,ans=-1e18;
	if(l<=mid)ans=max(ans,ask_pre(l,r,x*2,k));
	if(r>mid)ans=max(ans,ask_pre(l,r,x*2+1,k));
	return ans;
}
int ask_back(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r)return find_back(tr[x].root,k);
	int mid=(tr[x].l+tr[x].r)/2,ans=1e18;
	if(l<=mid)ans=min(ans,ask_back(l,r,x*2,k));
	if(r>mid)ans=min(ans,ask_back(l,r,x*2+1,k));
	return ans;
}
int ask_rank(int l,int r,int x,int k){
	if(l<=tr[x].l&&tr[x].r<=r)return find_rank(tr[x].root,k);
	int mid=(tr[x].l+tr[x].r)/2,ans=0;
	if(l<=mid)ans+=ask_rank(l,r,x*2,k);
	if(r>mid)ans+=ask_rank(l,r,x*2+1,k);
	return ans;
}
int ask_kth(int l,int r,int k){
	int ll=0,rr=1e8,ans;
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(k<ask_rank(l,r,1,mid-1)+1)rr=mid-1;
		else ll=mid+1,ans=mid;
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	srand((unsigned)time(0));
	cin>>n>>m;
	build(1,n,1);
	for(int i=1;i<=n;i++)cin>>a[i],seg_insert(1,i,a[i]);
	while(m--){
		int op,l,r,k;
		cin>>op>>l>>r;
		if(op==1)cin>>k,cout<<ask_rank(l,r,1,k-1)+1<<'\n';
		if(op==2)cin>>k,cout<<ask_kth(l,r,k)<<'\n';
		if(op==3)change(l,1,a[l],r),a[l]=r;
		if(op==4)cin>>k,cout<<ask_pre(l,r,1,k)<<'\n';
		if(op==5)cin>>k,cout<<ask_back(l,r,1,k)<<'\n';
	}
}

··· #include<bits/stdc++.h> #define int long long using namespace std; const int inf=2147483647; int m,n,cnt,a[50001]; struct node{ int val,key,l,r,size; }t[40000001]; struct tree{ int l,r,root; }tr[200001]; int newnode(int val) { t[++cnt].val=val; t[cnt].size=1; t[cnt].key=rand(); return cnt; } void push(int x){t[x].size=1+t[t[x].l].size+t[t[x].r].size;} void sq(int &x,int &y,int k,int p){ if(!p){ x=y=0; return ; } if(t[p].val<=k){ x=p; sq(t[p].r,y,k,t[p].r); } else{ y=p; sq(x,t[p].l,k,t[p].l); } push(p); } int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].key>t[y].key){ t[x].r=merge(t[x].r,y); push(x); return x; } else { t[y].l=merge(x,t[y].l); push(y); return y; } } void insert(int val,int &root){ int x,y; sq(x,y,val,root); root=merge(merge(x,newnode(val)),y); } void del(int val,int &root){ int x,y,z; sq(x,z,val,root); sq(x,y,val-1,x); root=merge(merge(x,t[y].l),merge(t[y].r,z)); } int find_pre(int &root,int k){ int x,y,z,ans; sq(x,y,k-1,root),z=x; while(z)ans=t[z].val,z=t[z].r; root=merge(x,y); return ans; } int find_back(int &root,int k){ int x,y,z,ans; sq(x,y,k,root),z=y; while(z)ans=t[z].val,z=t[z].l; root=merge(x,y); return ans; } int find_rank(int &root,int k){ int x,y,ans; sq(x,y,k,root); ans=t[x].size-1; root=merge(x,y); return ans; } void build(int l,int r,int x){ insert(inf,tr[x].root),insert(-inf,tr[x].root); tr[x].l=l;tr[x].r=r; if(l==r)return ; int mid=(l+r)/2; build(l,mid,x2);build(mid+1,r,x2+1); } void change(int p,int x,int kk,int k){ del(kk,tr[x].root),insert(k,tr[x].root); if(tr[x].l==tr[x].r)return ; int mid=(tr[x].l+tr[x].r)/2; if(p<=mid)change(p,x2,kk,k); else change(p,x2+1,kk,k); } void seg_insert(int x,int p,int k){ insert(k,tr[x].root); if(tr[x].l==tr[x].r)return ; int mid=(tr[x].l+tr[x].r)/2; if(p<=mid)seg_insert(x2,p,k); else seg_insert(x2+1,p,k); } int ask_pre(int l,int r,int x,int k){ if(l<=tr[x].l&&tr[x].r<=r)return find_pre(tr[x].root,k); int mid=(tr[x].l+tr[x].r)/2,ans=-1e18; if(l<=mid)ans=max(ans,ask_pre(l,r,x2,k)); if(r>mid)ans=max(ans,ask_pre(l,r,x2+1,k)); return ans; } int ask_back(int l,int r,int x,int k){ if(l<=tr[x].l&&tr[x].r<=r)return find_back(tr[x].root,k); int mid=(tr[x].l+tr[x].r)/2,ans=1e18; if(l<=mid)ans=min(ans,ask_back(l,r,x2,k)); if(r>mid)ans=min(ans,ask_back(l,r,x2+1,k)); return ans; } int ask_rank(int l,int r,int x,int k){ if(l<=tr[x].l&&tr[x].r<=r)return find_rank(tr[x].root,k); int mid=(tr[x].l+tr[x].r)/2,ans=0; if(l<=mid)ans+=ask_rank(l,r,x2,k); if(r>mid)ans+=ask_rank(l,r,x2+1,k); return ans; } int ask_kth(int l,int r,int k){ int ll=0,rr=1e8,ans; while(ll<=rr){ int mid=(ll+rr)/2; if(k<ask_rank(l,r,1,mid-1)+1)rr=mid-1; else ll=mid+1,ans=mid; } return ans; } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); srand((unsigned)time(0)); cin>>n>>m; build(1,n,1); for(int i=1;i<=n;i++)cin>>a[i],seg_insert(1,i,a[i]); while(m--){ int op,l,r,k; cin>>op>>l>>r; if(op==1)cin>>k,cout<<ask_rank(l,r,1,k-1)+1<<'\n'; if(op==2)cin>>k,cout<<ask_kth(l,r,k)<<'\n'; if(op==3)change(l,1,a[l],r),a[l]=r; if(op==4)cin>>k,cout<<ask_pre(l,r,1,k)<<'\n'; if(op==5)cin>>k,cout<<ask_back(l,r,1,k)<<'\n'; } } ···