萌新刚学Treap,求助大佬
查看原帖
萌新刚学Treap,求助大佬
231169
Laser_Crystal楼主2020/7/28 15:56

求助大佬

貌似是a=0的情况处理不好?

555求助

#include<bits/stdc++.h> 
using namespace std;
int n;
int T,R1,R2,size,S;
int x[100005],y[100005],z[100005];
bool f[100005];
int  res[100005];
struct node{
	int l,r,size,rnd,w;
	int v;
}tree1[100005],tree2[100005];
inline void update1(int k){tree1[k].size=tree1[tree1[k].l].size+tree1[tree1[k].r].size+tree1[k].w;}
inline void update2(int k){tree2[k].size=tree2[tree2[k].l].size+tree2[tree2[k].r].size+tree2[k].w;}
inline void Rt1(int &k)
{
	int t=tree1[k].l;tree1[k].l=tree1[t].r;tree1[t].r=k;
	tree1[t].size=tree1[k].size; update1(k);k=t;
}
inline void Rt2(int &k)
{
	int t=tree2[k].l;tree2[k].l=tree2[t].r;tree2[t].r=k;
	tree2[t].size=tree2[k].size; update2(k);k=t;
}
inline void Lt1(int &k)
{
	int t=tree1[k].r;tree1[k].r=tree1[t].l;tree1[t].l=k;
	tree1[t].size=tree1[k].size;update1(k);k=t;
}
inline void Lt2(int &k)
{
	int t=tree2[k].r;tree2[k].r=tree2[t].l;tree2[t].l=k;
	tree2[t].size=tree2[k].size;update2(k);k=t;
}
inline void insert1(int &k,int x)
{
	if(k==0) 
	{
		k=++size; 
		tree1[k].size=tree1[k].w=1;tree1[k].v=x;tree1[k].rnd=rand();	
		return;
	}
	tree1[k].size++;
	if(tree1[k].v==x) {tree1[k].w++;return;}
	if(x>tree1[k].v)
	{
		insert1(tree1[k].r,x);
		if(tree1[tree1[k].r].rnd<tree1[k].rnd) Lt1(k);
	} 
	else
	{
		insert1(tree1[k].l,x);
		if(tree1[tree1[k].l].rnd>tree1[k].rnd) Rt1(k);
	}	
}
inline void insert2(int &k,int x)
{
	if(k==0) 
	{
		k=++size; 
		tree2[k].size=tree2[k].w=1;tree2[k].v=x;tree2[k].rnd=rand();	
		return;
	}
	tree2[k].size++;
	if(tree2[k].v==x) {tree2[k].w++;return;}
	if(x>tree2[k].v)
	{
		insert2(tree2[k].r,x);
		if(tree2[tree2[k].r].rnd<tree2[k].rnd) Lt2(k);
	} 
	else
	{
		insert2(tree2[k].l,x);
		if(tree2[tree2[k].l].rnd>tree2[k].rnd) Rt2(k);
	}	
}
inline void del1(int &k,int x)
{
	if(k==0) return;
	if(tree1[k].v==x)
	{
		if(tree1[k].w>1) {tree1[k].w--;tree1[k].size--;return;}
		if(tree1[k].l*tree1[k].r==0) k=tree1[k].l+tree1[k].r;
		else if(tree1[tree1[k].l].rnd<tree1[tree1[k].r].rnd)  Rt1(k),del1(k,x);
		else Lt1(k),del1(k,x);
	}
	else if(x>tree1[k].v)  tree1[k].size--,del1(tree1[k].r,x);
	else tree1[k].size--,del1(tree1[k].l,x);
}
 void del2(int &k,int x)
{
	if(k==0) return;
	if(tree2[k].v==x)
	{
		if(tree2[k].w>1) {tree2[k].w--;tree2[k].size--;return;}
		if(tree2[k].l*tree2[k].r==0) k=tree2[k].l+tree2[k].r;
		else if(tree2[tree2[k].l].rnd<tree2[tree2[k].r].rnd)  Rt2(k),del2(k,x);
		else Lt2(k),del2(k,x);
	}
	else if(x>tree2[k].v)  tree2[k].size--,del2(tree2[k].r,x);
	else tree2[k].size--,del2(tree2[k].l,x);
}
inline int rk1(int k,int x)
{
	if(k==0) return 0;
	else if(tree1[k].v==x) return tree1[tree1[k].l].size+1;
	else if(x>tree1[k].v) return tree1[tree1[k].l].size+tree1[k].w+rk1(tree1[k].r,x);
	else return rk1(tree1[k].l,x);
}
inline int rk2(int k,int x)
{
	if(k==0) return 0;
	else if(tree2[k].v==x) return tree2[tree2[k].r].size+1;
	else if(x<tree2[k].v) return tree2[tree2[k].r].size+tree2[k].w+rk2(tree2[k].l,x);
	else return rk2(tree2[k].r,x);
}
int main()
{
	cin>>n;
	memset(f,0,sizeof(f));
	while(n--)
	{
		string c;
		cin>>c;
		if(c=="Add")
		{
			++S;
			scanf("%d%d%d",&x[S],&y[S],&z[S]);
			f[S]=1;
			if(x[S]>0)  
			{
				res[S]=floor((z[S]-y[S])/(1.0*x[S]))+1;
				insert1(R1,res[S]);
			}
			else if(x[S]==0)
			{
				if(y[S]>z[S]) T++;
			}
			else if(x[S]<0) 
			{
				res[S]=ceil((z[S]-y[S])/(x[S]*1.0))-1;
				insert2(R2,res[S]);
			}
		}
		else if(c=="Del")
		{
			int d; cin>>d; 
			if(f[d])
			{
				if((x[d]==0)&&(y[d]>z[d])) T--;
				else if(x[d]>0) del1(R1,res[d]);
				else del2(R2,res[d]);
				f[d]=0;
			}
		}
		else if(c=="Query")
		{
			int k; cin>>k;
			cout<<rk1(R1,k)+T+rk2(R2,k)<<endl;
		}
	}
	return 0;
}
2020/7/28 15:56
加载中...