uoj195 大森林

Link

Solution

很不错的数据结构题目！

首先要注意到，只要得到一个树木的最终形态，就可以回答与这棵树有关的所有询问。因为只存在在下面加点的操作，上方的点怎么也不会被影响到。

那就考虑如何得到每个树木的最终形态。

先把

Code

#include <bits/stdc++.h>
const int IN=1e7;
char inBuf[IN],*iptr=inBuf;
#define getchar() (*iptr==0 && (inBuf[fread(iptr=inBuf,1,IN,stdin)]=0,*iptr==0)?EOF:*iptr++)
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
const int OUT=1e7;
char outBuf[OUT],*optr=outBuf;
const char EOB=outBuf[OUT-1]=-1;
#define putchar(x) ((*optr==EOB && (fwrite(outBuf,1,OUT,stdout),optr=outBuf),*optr++)=(x))
struct Ostream {
	~Ostream() {
		fwrite(outBuf,1,optr-outBuf,stdout);
	}
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=1e5+11,MAXQ=2e5+11;
template <class T> inline
bool chkmx(T &a,T const &b) {
	return a<b?a=b,1:0;
}
template <class T> inline
bool chkmn(T &a,T const &b) {
	return a>b?a=b,1:0;
}
struct LCT {
	int Dist(int x,int y) {
		//2情况
		Node *px=node[x],*py=node[y];
		BeRoot(px);
		Touch(py);
		int res=py->sumv-LCA(px,py)->val;
		return res;
	}
	void LinkTo(int x,int fa) {
		BeRoot(node[x]);
		node[x]->fa=node[fa];
	}
	void CutOff(int x) {
		BeRoot(node[1]);
		Node *pos=node[x];
		Touch(pos);
		pos->Down();
		pos->son[0]=pos->son[0]->fa=null;
		pos->Up();
	}
	void Insert(int val) {
		node.push_back(new Node(val));
	}
	struct Node {
		Node *son[2],*fa;
		int sumv,val;
		bool rev;
		Node(int val):sumv(val),val(val),rev(0) {
			son[0]=son[1]=fa=null;
		}
		Node(bool):sumv(0),val(0),rev(0) {
			son[0]=son[1]=fa=0;
		}
		bool isRoot() {
			return fa->son[0]!=this && fa->son[1]!=this;
		}
		bool Kind() {
			return fa->son[1]==this;
		}
		void Rev() {
			std::swap(son[0],son[1]);
			rev^=1;
		}
		void Down() {
			if(rev) {
				son[0]->Rev();
				son[1]->Rev();
				rev=0;
			}
		}
		void Up() {
			sumv=son[0]->sumv+son[1]->sumv+val;
		}
	};
	static Node *null;
	std::vector<Node*> node;
	LCT() {
		node.push_back(null);
	}
	Node *LCA(Node *p1,Node *p2) {
		BeRoot(node[1]);
		Access(p1);
		return Access(p2);
	}
	static void Trans(Node *pos) {
		Node *fa=pos->fa,*grand=fa->fa;
		fa->Down();pos->Down();
		int d=pos->Kind();
		if(!fa->isRoot()) {
			grand->son[fa->Kind()]=pos;
		}
		pos->fa=grand;
		pos->son[!d]->fa=fa;fa->son[d]=pos->son[!d];
		pos->son[!d]=fa;fa->fa=pos;
		fa->Up();
	}
	static void Splay(Node *pos) {
		for(Node *fa;!pos->isRoot();Trans(pos)) {
			if(!(fa=pos->fa)->isRoot()) {
				Trans(fa->Kind()==pos->Kind()?fa:pos);
			}
		}
		pos->Up();
	}
	static void BeRoot(Node *pos) {
		Touch(pos);
		pos->Rev();
	}
	static void Touch(Node *pos) {
		Access(pos);
		Splay(pos);
	}
	static Node *Access(Node *pos) {
		static Node *pred;
		for(pred=null;pos!=null;pred=pos,pos=pos->fa) {
			Splay(pos);
			pos->Down();
			pos->son[1]=pred;
			pos->Up();
		}
		return pred;
	}
};
LCT::Node *LCT::null=new LCT::Node(true);
struct DarkOpt {
	int opt,pos,a,b,*Ans;
	DarkOpt(int opt,int pos,int a,int b,int *Ans=0):opt(opt),pos(pos),a(a),b(b),Ans(Ans) {}
	friend bool operator <(DarkOpt const &lhs,DarkOpt const &rhs) {
		return lhs.pos<rhs.pos || (lhs.pos==rhs.pos && lhs.opt<rhs.opt);
	}
};
int main() {
	/*
	   我想想
	   为每个1操作加入一个虚点作为生长节点
	   遍历每个子树
	 */
	int n,Q;is>>n>>Q;
	std::vector<DarkOpt> opt;opt.reserve(Q<<1);
	std::vector<int> Ans;Ans.reserve(Q);
	LCT lct;
	static int lbd[MAXQ],rbd[MAXQ],idr[MAXQ],reac,lastVi,noc;
	lbd[reac=1]=1;rbd[1]=n;
	idr[1]=1;
	lct.Insert(1);
	lbd[noc=2]=1;rbd[2]=n;
	lastVi=noc;
	lct.Insert(0);
	lct.LinkTo(2,1);
	for(int rep=1;rep<=Q;++rep) {
		int op;is>>op;
		switch(op) {
			case 0: {
				//newNode
				idr[++reac]=++noc;
				is>>lbd[reac]>>rbd[reac];
				lct.Insert(1);
				lct.LinkTo(idr[reac],lastVi);
			} break;
			case 1: {
				//changeGrow
				int l,r,x;is>>l>>r>>x;
				chkmx(l,lbd[x]);
				chkmn(r,rbd[x]);
				if(l<=r) {
					int newVi=++noc;
					lct.Insert(0);
					lct.LinkTo(newVi,lastVi);
					//这个修改没有生效的时候 是要连接到上一个虚点上的
					opt.push_back(DarkOpt(1,l,newVi,idr[x]));
					opt.push_back(DarkOpt(1,r+1,newVi,lastVi));
					lastVi=newVi;
				}
			} break;
			case 2: {
				int x,u,v;is>>x>>u>>v;
				Ans.push_back(-1);
				opt.push_back(DarkOpt(2,x,idr[u],idr[v],&Ans.back()));
			} break;
		}
	}
	std::sort(opt.begin(),opt.end());
	for(size_t i=0;i<opt.size();++i) {
		DarkOpt &o=opt[i];
		switch(o.opt) {
			case 1: {
				lct.CutOff(o.a);
				lct.LinkTo(o.a,o.b);
			} break;
			case 2: {
				*o.Ans=lct.Dist(o.a,o.b);
			} break;
		}
	}	
	for(size_t i=0;i<Ans.size();++i) {
		os<<Ans[i]<<'\n';
	}
	return 0;
}