fhq码风问题求调qwwwq
查看原帖
fhq码风问题求调qwwwq
371968
ningago寄寄人楼主2023/1/27 16:52

求助大佬,注释里的代码只可以过 7127-12 号点和 2121 号点。其它WA,改成现在这样(也就是题解普遍写法)就好了,我原来这种写法应该怎么改进才能过呀


...

int copynode(int k);

struct Tree
{
	int ls,rs;
	int key,val,sz,sum;
	bool lazy;
	void push()
	{
		ls = copynode(ls);
		rs = copynode(rs);
		ls ^= rs ^= ls ^= rs;
		lazy ^= 1;
	}
}tr[N * 20];

int idx;

#define lson(k) tr[k].ls
#define rson(k) tr[k].rs

int newnode(int val)
{
	tr[++idx].val = val;
	tr[idx].key = rnd();
	tr[idx].sz = 1;
	tr[idx].sum = val;
	return idx;
}

int copynode(int k)
{
	if(!k)
		return 0;
	tr[++idx] = tr[k];
	return idx;
}

void pushup(int k)
{
	tr[k].sz = tr[lson(k)].sz + tr[rson(k)].sz + 1;
	tr[k].sum = tr[lson(k)].sum + tr[rson(k)].sum + tr[k].val;
}

void pushdown(int k)
{
	if(tr[k].lazy)
	{
		tr[k].lazy = 0;
		lson(k) = copynode(lson(k));  //tr[lson(k)].push();
		rson(k) = copynode(rson(k));  //tr[rson(k)].push();
		std::swap(lson(k),rson(k));   //
		tr[lson(k)].lazy ^= 1;        //
		tr[rson(k)].lazy ^= 1;        //
	}
}

void split(int k,int sz,int &x,int &y)
{
	if(!k)
		x = y = 0;
	else
	{
		pushdown(k);
		if(tr[lson(k)].sz < sz)
		{
			x = copynode(k);
			split(rson(x),sz - tr[lson(k)].sz - 1,rson(x),y);
			pushup(x);
		}
		else
		{
			y = copynode(k);
			split(lson(y),sz,x,lson(y));
			pushup(y);
		}
	}
}

int merge(int x,int y)
{
	if(!x || !y)
		return x | y;
	if(tr[x].key < tr[y].key)
	{
		pushdown(x);
		rson(x) = merge(rson(x),y);
		pushup(x);
		return x;
	}
	else
	{
		pushdown(y);
		lson(y) = merge(x,lson(y));
		pushup(y);
		return y;
	}
}

int root[N];

signed main()
{
	scanf("%lld",&n);
	int lastans = 0;
	int t1 = 0,t2 = 0,t3 = 0;
	for(int i = 1,id,op,x,y;i <= n;i++)
	{
		scanf("%lld%lld%lld",&id,&op,&x);
		if(op != 2)
			scanf("%lld",&y);
		x ^= lastans,y ^= lastans;
		if(op == 1)
		{
			split(root[id],x,t1,t2);
			root[i] = merge(merge(t1,newnode(y)),t2);
		}
		else if(op == 2)
		{
			split(root[id],x,t1,t3);
			split(t1,x - 1,t1,t2);
			root[i] = merge(t1,t3);
		}
		else if(op == 3)
		{
			split(root[id],y,t1,t3);
			split(t1,x - 1,t1,t2);
			tr[t2].lazy ^= 1;  // tr[t2].push();
			root[i] = merge(merge(t1,t2),t3);
		}
		else if(op == 4)
		{
			split(root[id],y,t1,t3);
			split(t1,x - 1,t1,t2);
			printf("%lld\n",tr[t2].sum);
			lastans = tr[t2].sum;
			root[i] = merge(merge(t1,t2),t3);
		}
	}
	return 0;
}

不尽感激

2023/1/27 16:52
加载中...