BZOJ 3153 Sone1

Link

Solution

AAA树的模板题。然而调了很长时间

关于标记

在一个数据结构中，对于一条信息，不可以同时存在两个功能相同的标记覆盖到它，因为这样会使标记合并的过程紊乱。好吧我知道这是常识但我确确实实刚刚发现 对于的标记，因为需要同时修改链和子树，所以需要两种标记。 首先链的标记$mch$是没跑了，其次还需要一个修改子树的标记。 在翱犇和zky的论文和代码中，发现他们都是维护了子树中除了链之外的部分的标记$mre$。我想不通为什么，而且我还用直接记录整个子树的标记$mall$的方法AC了BZOJ3786，也没有发现什么问题。 于是我就写了$mch+mall$。 改到最后解决其它的所有问题之后狂WA不止。想了很长时间才领悟到这个十分显然的道理：$mch,mall$都修改了链的信息，那先来后到就不好安排了。虽然感性地认知一下，应该可以通过一些比较复杂的分类讨论搞定，但我还是选择了改成$mch+mre$。

关于标记下传

写的时候总结出一个原则：只有在树的结构修改的时候才需要，这样就避免了通过DFS或者手工栈预先下传一条链的标记(虽然复杂度不受影响但是我觉得代码不优美) 在，其他的部分也可以遵循这个原则从而避免DFS，但是有一个地方是没有办法的：在删除虚子树的时候。 因为在虚子树的中，只能旋转虚节点。当一个点要被切掉的时候，必须把上方所有的标记都传过来。如果可以转它的话就好办了，但问题就出在这。 所以经过很长时间的思考，我只好接受了这个现实：从待删除虚子树到其真正父节点的路径上的标记只能手动下传。这个过程还要注意：一定要先向上跳一下到一个虚节点上，再开始不断向上跳。否则的话根本不会向上走。 还有一个坑点：在存在$rev$标记的中，自上而下查找也必须要，因为$rev$前后树是完全不同的，不就会找到错误的节点。

Code

同样的东西，人家写200+，我写400+。吐槽自己一下。

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
using std::max;
using std::min;
using std::pair;
using std::make_pair;
using std::fill;
using std::swap;
const int MAXN=100000+11,INF=INT_MAX;

struct Mark
{
	int k,b;
	Mark(int k=1,int b=0):k(k),b(b){}
	int operator ()(int x,int sz=1) {return k*x+sz*b;}
	Mark &operator +=(Mark a)
	{
		int dk=k*a.k,db=b*a.k+a.b;
		k=dk,b=db;
		return *this;
	}
	bool operator !=(Mark a) {return k!=a.k || b!=a.b;}
}nMark;
struct Data
{
	int minv,maxv,sumv,sz;
	Data(int minv=INF,int maxv=-INF,int sumv=0,int sz=0):minv(minv),maxv(maxv),sumv(sumv),sz(sz){}
	Data &operator +=(Mark b)
	{
		if(sz)
		{
			minv=b(minv);
			maxv=b(maxv);
			sumv=b(sumv,sz);
		}
		return *this;
	}
}nData;

Data operator +(Data a,Data b)
{
	return Data(min(a.minv,b.minv),
				max(a.maxv,b.maxv),
				a.sumv+b.sumv,
				a.sz+b.sz);
}
namespace AAA
{
	const int SIZE=MAXN<<2;
	struct Node
	{
		Node *son[4],*fa;
		Data se,re,ch,all;
		Mark mch,mre;
		bool rev,imag;
		int kind()
		{
			for(int i=0;i<4;++i)
				if(fa->son[i]==this)
					return i;
			assert(0);
		}
		bool isRoot(int type) {return type?(!fa->imag || !imag):(fa->son[0]!=this && fa->son[1]!=this);}
		Node()
		{
			fill(son,son+4,fa=0);
			se=re=ch=all=nData;
			mch=mre=nMark;
			rev=imag=0;
		}
		void Link(int d,Node *s)
		{
			son[d]=s;
			s->fa=this;
		}
		void Sets(Node *s,int d)
		{
			Down();
			son[d]=s;
			s->fa=this;
			Up();
		}
		void Rev();
		void Edit(Mark,int);
		void Up();
		void Down();
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,**BIN=(Node**)malloc(SIZE*sizeof(Node*)),*null=new(ME++) Node,*node[MAXN];
	int root;
	Node *newNode(int val=INF)
	{
		Node *cur=*BIN?*BIN--:ME++;
		fill(cur->son,cur->son+4,cur->fa=null);
		cur->re=nData;
		cur->mch=cur->mre=nMark;
		cur->rev=0;
		if(val==INF)
		{
			cur->se=cur->all=cur->ch=nData;
			cur->imag=1;
		}
		else
		{
			cur->se=cur->all=cur->ch=Data(val,val,val,1);
			cur->imag=0;
		}
		return cur;
	}
	void delNode(Node *&pos)
	{
		*++BIN=pos;
		pos=0;
	}
	void Node::Rev()
	{
		if(this==null) return;
		swap(son[0],son[1]);
		rev^=1;
	}
	const int E_ALL=0,E_CH=1,E_RE=2;
	void Node::Edit(Mark f,int type)
	{
		if(this==null) return;
		if(type==E_ALL || type==E_CH)
		{
			se+=f;
			mch+=f;
			ch+=f;
		}
		if(type==E_ALL || type==E_RE)
		{
			mre+=f;
			re+=f;
		}
		all=ch+re;
	}
	void Node::Up()
	{
		ch=son[0]->ch+son[1]->ch+se;
		re=son[0]->re+son[1]->re+son[2]->all+son[3]->all;
		all=ch+re;
	}
	void Node::Down()
	{
		if(rev)
		{
			son[0]->Rev();
			son[1]->Rev();
			rev=0;
		}
		if(mre!=nMark)
		{
			son[0]->Edit(mre,E_RE);
			son[1]->Edit(mre,E_RE);
			son[2]->Edit(mre,E_ALL);
			son[3]->Edit(mre,E_ALL);
			mre=nMark;
		}
		if(mch!=nMark)
		{
			son[0]->Edit(mch,E_CH);
			son[1]->Edit(mch,E_CH);
			mch=nMark;
		}

	}
	void Trans(Node *pos)
	{
		Node *fa=pos->fa,*grf=fa->fa;
		fa->Down(),pos->Down();
		int d=pos->kind();
		if(grf!=null)
			grf->son[fa->kind()]=pos;
		pos->fa=grf;
		fa->Link(d,pos->son[d^1]);
		pos->Link(d^1,fa);
		fa->Up();
	}
	const int S_LCT=0,S_AAA=2;
	void Splay(Node *pos,int type)
	{
		while(!pos->isRoot(type))
		{
			Node *fa=pos->fa;
			if(!fa->isRoot(type))
				Trans(fa->kind()==pos->kind()?fa:pos);
			Trans(pos);
		}
		pos->Up();
	}
	void AddVirt(Node *pos,Node *fa)
	{
		if(pos==null) return;
		fa->Down();
		for(int i=2;i<4;++i)
			if(fa->son[i]==null)
			{
				fa->Sets(pos,i);
				return;
			}
		while(fa->son[2]->imag)
			fa=fa->son[2];
		Splay(fa,S_AAA);
		Node *vi=newNode();
		vi->Link(2,fa->son[2]);
		vi->Link(3,pos);
		fa->Sets(vi,2);
		Splay(vi,S_AAA);
	}
	void DelVirt(Node *pos)
	{
		if(pos==null) return;
		static Node **top=(Node**)malloc(SIZE*sizeof(Node*));
		for(Node *p=pos->fa;p->imag;p=p->fa) *++top=p;
		if(*top) (*top)->fa->Down();
		for(;*top;top--) (*top)->Down();
		Node *fa=pos->fa;
		int d=pos->kind();
		if(fa->imag)
		{
			fa->fa->Sets(fa->son[d^1],fa->kind());
			Splay(fa->fa,S_AAA);
			delNode(fa);
		}
		else
		{
			fa->Sets(null,d);
			Splay(fa,S_AAA);
		}
		pos->fa=null;
	}
	void Access(Node *pos)
	{
		Node *pred=null;
		while(pos!=null)
		{
			Splay(pos,S_LCT);
			AddVirt(pos->son[1],pos);
			DelVirt(pred);
			pos->Sets(pred,1);
			pred=pos;
			for(pos=pos->fa;pos->imag;pos=pos->fa);
		}
	}
	void Touch(Node *pos)
	{
		Access(pos);
		Splay(pos,S_LCT);
	}
	void BeRoot(Node *pos)
	{
		Touch(pos);
		pos->Rev();
	}
	void Link(Node *p1,Node *p2)
	{
		BeRoot(p1);
		Touch(p2);
		AddVirt(p1,p2);
	}
	void Cut(Node *p1,Node *p2)
	{
		BeRoot(p1);
		Touch(p2);
		p2->Sets(null,0);
		p1->fa=null;
	}
	Node *FindRoot(Node *pos)
	{
		Touch(pos);
		while(pos->son[0]!=null) 
		{
			pos->Down();
			pos=pos->son[0];
		}
		Splay(pos,S_LCT);
		return pos;
	}
	Node *FindFa(Node *pos)
	{
		Touch(pos);
		pos=pos->son[0];
		if(pos==null) return 0;
		while(pos->son[1]!=null) 
		{
			pos->Down();//Down!!!!!!!
			pos=pos->son[1];
		}
		Splay(pos,S_LCT);
		return pos;
	}
	void ChangeFather(int pos,int father)
	{
		if(pos==root) return;
		Node *fa=FindFa(node[pos]);
		Cut(fa,node[pos]);
		if(FindRoot(node[pos])!=FindRoot(node[father]))
			Link(node[pos],node[father]);
		else
			Link(node[pos],fa);
	}
	namespace Chain
	{
		Data Query(int p1,int p2)
		{
			BeRoot(node[p1]);
			Touch(node[p2]);
			return node[p2]->ch;
		}
		void Edit(int p1,int p2,Mark f)
		{
			BeRoot(node[p1]);
			Touch(node[p2]);
			node[p2]->Edit(f,E_CH);
		}
	}
	namespace Sub
	{
		Data Query(int rt)
		{
			Touch(node[rt]);
			return node[rt]->se+node[rt]->son[2]->all+node[rt]->son[3]->all;
		}
		void Edit(int rt,Mark f)
		{
			Touch(node[rt]);
			node[rt]->se+=f;
			node[rt]->son[2]->Edit(f,E_ALL);
			node[rt]->son[3]->Edit(f,E_ALL);
		}
	}
}using namespace AAA;
int main()
{
	static int w[MAXN],edge[MAXN][2];
	int n,m;get(n),get(m);
	for(int i=1;i<=n-1;++i)
		get(edge[i][0]),get(edge[i][1]);
	for(int i=1;i<=n;++i)
	{
		get(w[i]);
		node[i]=newNode(w[i]);
	}
	get(root);
	for(int i=1;i<=n-1;++i)	Link(node[edge[i][0]],node[edge[i][1]]);
	for(int i=1;i<=m;++i)
	{
		int opt,x,y,z,Ans;get(opt);
		Data res;
		BeRoot(node[root]);
		switch(opt)
		{
			case 0:
			case 5:
				get(x),get(y);
				Sub::Edit(x,Mark(opt==0?0:1,y));
				break;
			case 1:
				get(root);
				break;
			case 2:
			case 6:
				get(x),get(y),get(z);
				Chain::Edit(x,y,Mark(opt==2?0:1,z));
				break;
			case 3://min
			case 4://max
			case 11://sum
				get(x);
				res=Sub::Query(x);
				switch(opt)
				{
					case 3:Ans=res.minv;break;
					case 4:Ans=res.maxv;break;
					case 11:Ans=res.sumv;break;
				}
				put(Ans),putchar('\n');
				break;
			case 7://min
			case 8://max
			case 10://sum
				get(x),get(y);
				res=Chain::Query(x,y);
				switch(opt)
				{
					case 7:Ans=res.minv;break;
					case 8:Ans=res.maxv;break;
					case 10:Ans=res.sumv;break;
				}
				put(Ans),putchar('\n');
				break;
			case 9:
				get(x),get(y);
				ChangeFather(x,y);
				break;
		}
	}
	return 0;
}