平衡树板子萌新求调QWQ,样例未过!!!
查看原帖
平衡树板子萌新求调QWQ,样例未过!!!
1270230
Phigeon楼主2025/1/21 20:58

以下是本蒟蒻的代码,de了半天没调出来

#include<bits/stdc++.h>
using namespace std;

const int maxn=500005; 

struct node{
	int pri,key,siz,lc,rc;
}t[maxn];

int tot,rt;

void pushup(int x){
	t[x].siz=t[t[x].lc].siz+t[t[x].rc].siz+1;
}

void splitK(int u,int k,int &x,int &y){
	if(!u) return (void)(x=y=0);
	if(t[u].key<=k){
		splitK(t[u].rc,k,t[u].rc,y);
		x=u;
		pushup(x);
	}
	else{
		splitK(t[u].lc,k,x,t[u].lc);
		y=u;
		pushup(y);
	}
}

void splitS(int u,int k,int &x,int &y){
	if(!u) return (void)(x=y=0);
	if(t[t[u].lc].siz<k){
		splitS(t[u].rc,k-t[t[u].lc].siz-1,t[u].rc,y);
		x=u;
		pushup(x);
	}
	else{
		splitS(t[u].lc,k,x,t[u].lc);
		y=u;
		pushup(y);
	}
}

int merge(int x,int y){
	if(!x || !y) return x|y;
	if(t[x].pri>t[y].pri){
		t[x].rc=merge(t[x].rc,y);
		pushup(x);
		return x;
	}
	else{
		t[x].lc=merge(x,t[x].lc);
		pushup(y);
		return y;
	}
}

int newnode(int x){
	t[++tot]={rand(),x,1,0,0};
	return tot;
}

void ins(int x){
	int a,b;
	splitK(rt,x,a,b);
	rt=merge(a,merge(newnode(x),b));
}

void del_all(int x){
	int a,b,c;
	splitK(rt,x-1,a,b);
	splitK(b,x,b,c);
	rt=merge(a,c);
}

void del(int x){
	int a,b,c;
	splitK(rt,x-1,a,b);
	splitS(b,1,b,c);
	rt=merge(a,c);
}

int qrk(int x){
	int a,b;
	splitK(rt,x-1,a,b);
	int ans=t[a].siz+1;
	rt=merge(a,b);
	return ans;
}

int qnb(int x){
	int a,b;
	splitS(rt,x,a,b);
	int p=a;
	while(t[p].rc) p=t[p].rc;
	rt=merge(a,b);
	return t[p].key;
}

int pre(int x){
	return qnb(qrk(x)-1);
}

int suf(int x){
	return qnb(qrk(x+1));
}

int main(){
	int n;cin>>n;
	while(n--){
		int op,x;
		cin>>op>>x;
		if(op==1) ins(x);
		if(op==2) del(x);
		if(op==3) cout<<qrk(x)<<'\n';
		if(op==4) cout<<qnb(x)<<'\n';
		if(op==5) cout<<pre(x)<<'\n';
		if(op==6) cout<<suf(x)<<'\n';
	}
	return 0;
}

求各位大佬指点QWQ

2025/1/21 20:58
加载中...