关于函数默认值的问题
查看原帖
关于函数默认值的问题
302750
Main_WF楼主2022/7/19 20:28

如果想要给insert()和remove()两个函数的int &x赋值上默认值root,应该如何码?

struct Treap
{	
	int tot,root,c[maxn],s[maxn],v[maxn],r[maxn],ch[maxn][2];
	inline int New(int x){++tot;v[tot]=x,r[tot]=rand(),c[tot]=s[tot]=1;return tot;}
		
	inline void up(int x){s[x]=s[ch[x][0]]+s[ch[x][1]]+c[x];}
	
	inline void init(){root=New(-INF),ch[root][1]=New(INF),up(root);}
	
	inline void ro(int &x,int d){int y=ch[x][d^1];ch[x][d^1]=ch[y][d];ch[y][d]=x;x=y;up(ch[x][d]),up(x);}
		
	inline void insert(int &x,int y)
	{
		if(!x){x=New(y);return;}
		if(y==v[x])
			c[x]++;
		else
		{
			int d=y>v[x];
			insert(ch[x][d],y);
			if(r[x]<r[ch[x][d]])
				ro(x,d^1);
		}
		up(x);
	}
		
	inline void remove(int &x,int y) 
	{
		if(!x)return;
		if(v[x]==y)
		{
			if(c[x]>1){c[x]--,up(x);}
			else if(ch[x][0]||ch[x][1])
			{
				if(!ch[x][1]||r[ch[x][1]]<r[ch[x][0]])
					ro(x,1),remove(ch[x][1],y);
				else
					ro(x,0),remove(ch[x][0],y);
			}
			else	x=0;
			up(x);
			return;
		}
		int d=y>v[x];remove(ch[x][d],y);up(x);
	}
	
	inline int rank(int x,int y) 
	{
		if(!x)
			return 0;
		if(v[x]==y)
			return s[ch[x][0]];
		else if(v[x]>y)
			return rank(ch[x][0],y);
		else
			return s[ch[x][0]]+c[x]+rank(ch[x][1],y);
	}
	inline int val(int x,int k) 
	{
		if(!x)
			return INF;
		if(k<=s[ch[x][0]])
			return val(ch[x][0],k);
		else if(k<=s[ch[x][0]]+c[x])
			return v[x];
		else
			return val(ch[x][1],k-(s[ch[x][0]]+c[x]));
	} 
	inline int get_pre(int y) 
	{
		int x=root,pre;
		while(x)
		{
			if(v[x]<y) 
				pre=v[x],x=ch[x][1];
			else
				x=ch[x][0];
		}
		return pre;
	}
	
	inline int get_suc(int y) 
	{
		int x=root,suc;
		while(x)
		{
			if(v[x]>y)
				suc=v[x],x=ch[x][0];
			else
				x=ch[x][1];
		}
		return suc;
	}
}T;
2022/7/19 20:28
加载中...