FHQ_Treap求调
查看原帖
FHQ_Treap求调
935908
zengziqvan楼主2024/6/9 11:19

样例未过,RE了。

#include <bits/stdc++.h>
#include <unistd.h>
#define ll long long
#define ull unsigned long long
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
using namespace std;
const int N=2e5+10; 
int n,k,tot,root;
struct Node {
	int ls,rs;
	int val,key,siz; 
}t[N];
void push_up(int p) {
	t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+1;
}
void Spilt(int p,int x,int &l,int &r) {
	if(!p) return (void)(l=r=0);
	if(t[p].val<=x) l=p,Spilt(t[p].rs,x,t[p].rs,r);
	else r=p,Spilt(t[p].ls,x,l,t[p].ls);
	push_up(p);
}
int Merge(int l,int r) {
	if(!l||!r) return l+r;
	if(t[l].key<=t[r].key) return t[r].ls=Merge(l,t[r].ls),push_up(r),r;
	else return t[l].rs=Merge(t[l].rs,r),push_up(l),l;
}
void Make(int x) {
	t[++tot]={0,0,x,rand(),1};
}
int Insert(int x) {
	int l,r;
	Spilt(root,x,l,r),Make(x);
	root=Merge(Merge(l,tot),r);
	return tot;
}
int Erase(int x) {
	int l,r,mid;
	Spilt(root,x,l,r);
	Spilt(l,x-1,l,mid);
	mid=Merge(t[mid].ls,t[mid].rs);
	return root=Merge(Merge(l,mid),r);
} 
int kth(int p,int k) {
	if(t[t[p].ls].siz+1==k) return p;
	if(k<=t[t[p].ls].siz) return kth(t[p].ls,k);
	return kth(t[p].rs,k-t[t[p].ls].siz-1);
}
int getid(int x) {
	int l,r;
	Spilt(root,x-1,l,r);
	int res=t[l].siz+1;
	root=Merge(l,r);
	return res;
}
int lst(int x) {
	int l,r;
	Spilt(root,x-1,l,r);
	int res=t[kth(l,t[l].siz)].val;
	root=Merge(l,r);
	return res;
}
int nxt(int x) {
	int l,r;
	Spilt(root,x,l,r);
	int res=t[kth(r,1)].val;
	root=Merge(l,r);
	return res;
}
int main() {
//	srand(time(0));
	cin>>n;
	while(n--) {
		int op,x;
		cin>>op>>x;
		if(op==1) Insert(x);
		if(op==2) Erase(x);
		if(op==3) cout<<getid(x)<<"\n";
		if(op==4) cout<<t[kth(root,x)].val<<"\n";
		if(op==5) cout<<lst(x)<<"\n";
		if(op==6) cout<<nxt(x)<<"\n";
	}	
	return 0;
}
2024/6/9 11:19
加载中...