萌新刚学 OI,求助 TLE+MLE 双开花的 FHQ-treap
查看原帖
萌新刚学 OI,求助 TLE+MLE 双开花的 FHQ-treap
298549
SIXIANG32楼主2021/1/27 21:02
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
struct FHQ_treap{
	int tot,root;
	struct node{
		int ls,rs,val,siz,cnt,rnd;
	}T[100010];
	void FHQ(){tot=root=0;}
	void updata(int x){T[x].siz=T[T[x].ls].siz+T[T[x].rs].siz+T[x].cnt;}
	void split(int now,int &a,int &b,int val)
	{
		if(!now){a=b=0;return ;}
		if(T[now].val<=val)a=now,split(T[now].rs,T[now].rs,b,val);
		else b=now,split(T[now].ls,a,T[now].ls,val);
		updata(now);
	}
	int merge(int a,int b)
	{
		if(!a||!b)return a|b;
		if(T[a].rnd<T[b].rnd){T[a].rs=merge(T[a].rs,b),updata(a);return a;}
		else{T[b].ls=merge(a,T[b].ls),updata(b);return b;}
	}
	int new_node(int val)
	{
		T[++tot].val=val,T[tot].siz=T[tot].cnt=1,T[tot].rnd=rand(); 
		return tot;
	}
	void insert(int val)
	{
        int x,y,z;
		split(root,x,y,val);
		root=merge(merge(x,new_node(val)),y);
	}
	void erase(int val)
	{
        int x,y,z;
		split(root,x,y,val);
		split(root,y,z,val-1);
		y=merge(T[y].ls,T[y].ls);
		root=merge(x,z);
	}
	int find_val(int now,int rank)
	{
		while(233)
		{
			if(rank<=T[T[now].ls].siz)now=T[now].ls;
			else if(rank==T[T[now].ls].siz+T[now].cnt)return T[now].val;
			else rank=rank-T[T[now].ls].siz-T[now].cnt,now=T[now].rs;
		}
	}
	int find_rank(int q)
	{
        int x,y,z;
		split(root,x,y,q-1);
		int ans=T[x].siz+1;
		root=merge(merge(x,y),z);	
		return ans;
	}
	int find_pre(int q)
	{
        int x,y,z;
		split(root,x,y,q-1);
		int ans=find_val(x,T[x].siz);
		root=merge(x,y);
		return ans;
	}
	int find_nxt(int q)
	{
        int x,y,z;
		split(root,x,y,q);
		int ans=find_val(y,1);
		root=merge(x,y);
		return ans;
	}
}FHQ;
int main()
{
	srand(time(0));
	int m;
	cin>>m;
	FHQ.FHQ();
	while(m--)
	{
		int opt,x;
		cin>>opt>>x;
		if(opt==1) FHQ.insert(x);
		else if(opt==2) FHQ.erase(x);
		else if(opt==3) cout<<FHQ.find_rank(x)<<endl;
		else if(opt==4) cout<<FHQ.find_val(FHQ.root,x)<<endl;
		else if(opt==5) cout<<FHQ.find_pre(x)<<endl;
		else if(opt==6) cout<<FHQ.find_nxt(x)<<endl;
	}
}

就很不对,真的没找到惹嘤嘤嘤。
如果是手残错误轻喷嘤嘤嘤

2021/1/27 21:02
加载中...