初学fhq-Treap MLE 60pts 求助
查看原帖
初学fhq-Treap MLE 60pts 求助
443675
紊莫turtle楼主2023/1/7 15:19

参考了:
https://www.luogu.com.cn/discuss/514163

感觉可能是类似的问题,按照上贴检查了一下就20->60
求调:

//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define mkpr make_pair
#define fi first
#define se second
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(int x){write(x);putchar('\n');}
inline void writesp(int x){write(x);putchar(' ');}
inline int lowbit(int x) {return x&(-x);}
typedef pair<int,int> Pair;
const int N=100005;
struct Tree{int l,r,val,siz,rnd;} a[N];
int n,tot,root,x,y,z;
inline void pushup(int p){a[p].siz=a[a[p].l].siz+a[a[p].r].siz+1;}  
void split(int p,int k,int &x,int &y){
	if(!p){x=y=0;return ;}
	if(a[p].val<=k) {x=p;split(a[p].r,k,a[p].r,y);}
	else {y=p;split(a[p].l,k,x,a[p].l);}
	pushup(p);
}
int merge(int u,int v){
	if(!u||!v) return u|v;
	if(a[u].rnd<a[v].rnd){
		a[u].r=merge(a[u].r,v);
		pushup(u);return u;
	}else{
		a[v].l=merge(u,a[v].l);
		pushup(v);return v;
	}
}
int New(int v){
	a[++tot].val=v;a[tot].siz=1,a[tot].rnd=rand();
    return tot;
}
void Insert(int v){
	split(root,v,x,y);
	root=merge(merge(x,New(v)),y);
}
void Delete(int v){
	split(root,v,x,y);split(x,v-1,x,z);
	z=merge(a[z].l,a[z].r);
	root=merge(merge(x,y),z);
}
int Qkth(int p,int k){
	while(1){
		if(k<=a[a[p].l].siz) p=a[p].l;
		else if(k==a[a[p].l].siz+1) return p;
		else k=k-a[a[p].l].siz-1,p=a[p].r;
	}
}
int Qfront(int v){
	split(root,v-1,x,y);
	int rt=a[Qkth(x,a[x].siz)].val;
	root=merge(x,y);
	return rt;
}
int Qnxt(int v){
	split(root,v,x,y);
	int rt=a[Qkth(y,1)].val;
	root=merge(x,y);
	return rt;
}
int Qrank(int v){
	split(root,v-1,x,y);
	int rt=a[x].siz+1;
	root=merge(merge(x,y),z);
	return rt;
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;srand(time(0));
	while(n--){
		int op,v;cin>>op>>v;
		if(op==1) Insert(v);
		else if(op==2) Delete(v);
		else if(op==3) cout<<Qrank(v)<<'\n';
		else if(op==4) cout<<a[Qkth(root,v)].val<<'\n';
		else if(op==5) cout<<Qfront(v)<<'\n';
		else cout<<Qnxt(v)<<'\n';
	}
    return 0;
}
2023/1/7 15:19
加载中...