【BZOJ 4573】[ZJOI2016] 大森林

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4573
数据生成器：http://paste.ubuntu.com/24208883/
神犇题解Ⅰ：http://blog.csdn.net/werkeytom_ftd/article/details/56671440
神犇题解Ⅱ：http://sxy-cnyali.logdown.com/posts/1398090-zjoi2016

解题报告

这题似乎有三种做法？我们这里只讨论$LCT$的做法

首先将询问离线，对于每一次0/1号操作，都新建一个结点
并且挂到它之前的最后一个1号操作对应的节点下

我们考虑对于第$i$棵树的某个结点$j$
在最终形态中，其一定是在对在$i$树有效最后一个$1$号操作指定的点下面
所以我们对于一个$1$号操作的结点，若其生效了，那么将其整个子树全部移到指定结点
若其失效了，我们将其整个子树移到它之前的最晚一个$1$号操作对应的节点下
这样显然就可以回答询问了，搞几次$access$操作即可

于是问题变成如何动态维护一棵树，要求移动子树、询问根到某个点的路径上权值和
这个显然可以无脑$LCT$，于是我们就在$O(n \log n)$的时间复杂度内解决这个问题啦！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;

int n,m,num[N],l[N],r[N],last[N],to[N],ans[N],id[N];
vector<int> ins[N],del[N],q[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Link_Cut_Tree{
	struct Node{int val,sum,fa,ch[2];}p[N];
	int cnt;
	public:
		inline int NewNode(int v) {
			p[cnt+1].sum = p[cnt+1].val = v;
			return ++cnt;
		}
		inline void modify(int w, int t) {
			cut(num[w]); 
			if (t == 1) link(num[w], id[to[w]]);
			else link(num[w], last[w]);
		}
		inline int query(int x) {
			int u = id[l[N-x]], v = id[r[N-x]], ret;
			access(u); splay(u); ret = p[u].sum;
			x = access(v); splay(v); ret += p[v].sum;
			access(x); splay(x); ret -= p[x].sum << 1;
			return abs(ret);
		}
		inline void link(int a, int b) {
			splay(a); p[a].fa = b;
		}
		inline void cut(int x) {
			access(x); splay(x); 
			p[x].ch[0] = p[p[x].ch[0]].fa = 0;
			maintain(x); 
		}
	private:
		inline void maintain(int w) {
			p[w].sum = p[w].val + p[p[w].ch[0]].sum + p[p[w].ch[1]].sum;
		}
		inline bool IsRoot(int w) {
			return !p[w].fa || (p[p[w].fa].ch[0] != w && p[p[w].fa].ch[1] != w);
		}
		inline void rotate(int x) {
			int y=p[x].fa,z=p[y].fa,t=p[y].ch[1]==x;
			if (!IsRoot(y)) p[z].ch[p[z].ch[1]==y] = x;
			p[y].ch[t] = p[x].ch[t^1]; p[p[x].ch[t^1]].fa = y;
			p[x].ch[t^1] = y; p[x].fa = z; p[y].fa = x;
			maintain(y); maintain(x);
		}
		inline void splay(int x) {
			for (int f,ff;!IsRoot(x);) {
				f = p[x].fa; ff = p[f].fa;
				if (IsRoot(f)) rotate(x);
				else {
					if ((p[ff].ch[0]==f)^(p[f].ch[0]==x)) rotate(x),rotate(x);
					else rotate(f),rotate(x);
				}
			}
		}
		inline int access(int x) {
			for (int last=0;;last=x,x=p[x].fa) 
				if (x) splay(x), p[x].ch[1] = last, maintain(x);
				else return last;
		}
}lct;

int main() {
	n = read(); m = read();
	int pre = lct.NewNode(0); id[1] = lct.NewNode(1);
	lct.link(pre, id[1]); l[1] = 1; r[1] = n;
	for (int i=1,opt,ll,rr,x,tot=1;i<=m;i++) {
		if (!(opt=read())) {
			id[++tot] = lct.NewNode(1);
			l[tot] = read(); r[tot] = read();
			lct.link(id[tot], pre);
		} else if (opt == 1) {
			ll = read(); rr = read(); to[i] = x = read(); 
			ll = max(ll, l[x]); rr = min(rr, r[x]);
			if (ll <= rr) {
				ins[ll].push_back(i), del[rr].push_back(i);
				num[i] = lct.NewNode(0); lct.link(num[i], pre); 
				last[i] = pre; pre = num[i];
			} 
		} else {
			x = read(); l[N-i] = read(); r[N-i] = read();
			q[x].push_back(i);
		}
	}
	memset(ans,-1,sizeof(ans));
	for (int i=1;i<=n;i++) {
		for (int j=ins[i].size()-1;~j;j--) lct.modify(ins[i][j], 1);
		for (int j=q[i].size()-1;~j;j--) ans[q[i][j]] = lct.query(q[i][j]);
		for (int j=del[i].size()-1;~j;j--) lct.modify(del[i][j], -1);
	}
	for (int i=1;i<=m;i++) (~ans[i])? printf("%d\n",ans[i]),1: 0; 
	return 0;
}