[ZJOI2016]大森林

本文主要是介绍[ZJOI2016]大森林，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

复盘 $\text{zzq}$ 讲的题，来写篇题解~~祸害社会~~。

可能是更好做的想法。

Description

给定 $n$ 棵树和 $m$ 次操作，其中每棵树均有一个初始节点（并设定为“生长节点”），操作格式有三种：

给定 $l$ 和 $r$ ，让区间 $[l,\ r]$ 内所有树的生长节点下添加一个子节点，子节点序号为上次 $1$ 操作加的新点的序号 $+1$ 。
给定 $l$ ，$r$ 和 $x$ ，让区间 $[l,\ r]$ 的树的生长节点全部改到 $x$ ，如果该树不存在 $x$ 则不产生影响。
给定 $x$ ，$u$ 和 $v$ ，查询第 $x$ 棵树上 $u$ 和 $v$ 之间的距离，保证该树存在 $u$ 和 $v$ 。

$n \leq 10 ^ 5,\ m \leq 2 \cdot 10 ^ 5$

Analysis

啊啊你说老师这题我会用 $\text{LCT}$ 维护建树，好家伙直接 $O(n ^ 2 \log n)$ 就做完了。

那显然是不行的。

这玩意想要在先做是没什么可能的了，先离线。

看看 $1$ 操作，乍一读感觉书上点的序号都是依序增加的。但是不对，序号为上次 $1$ 操作加的新点的序号 $+1$ ，什么意思，就是一个点 $x$ 的出现只会在一个区间。然后一看操作都是区间修改，单点查询，噢，应该是可以用扫描线的。

更具体一点就是按照下标为第一关键字，时间戳为第二关键字，把所有操作排序。

差不多分析完了，准备实操。

Solution

当然前面说的暴力空间也是会炸飞，所以总的只能建一棵树，这就需要考虑相邻两棵树之间的差异。

差异主要就是两个区间操作带来的：

对于操作 $1$ ，我们先前提到每种操作是有一个适用范围的，所以对适用范围去交之后加/删点？？

其实也完全不需要，反正查询保证了两点必然存在，多那么几个根本不存在的点也不会影响最终路径上点的数量，所以这个就嗯加就行了。

对于操作 $2$ ，我们可能需要一个能够比较灵活的点能够把目标换来换去的那种，考虑建虚点。

所以大概我们可以在区间开始的时候把虚点连到原先修改出生结点的地方，区间结束的时候在连回去。

这么一看，能支持连边删边还要统计树上距离的， $\text{LCT}$ 是比较实用的了，只不过要把边权改成点权，本质上其实差不多。

所以这样就有了一个很直接的想法：

对于每次操作 $2$ 都去建一个虚点，点权为零，然后把出生节点设为这个虚点，这样的话除了第一个虚点连的是初始节点，其他都连向的是上一个虚点。

所以如果按照时间戳来的话，只要每次加入一个新区间的时候把对应的虚点连到操作本身该连的节点上，脱离一个区间的时候连回去就行了。

但是因为边权改成了点权，所以对应的路径长度就需要考虑 $lca$ 在原树上的 $fa$ ，所以树的形态就不能轻易改变，我们就需要不换根 $\text{LCT}$ ，不会，摆~

咋办嘞，规避不了考虑原树 $lca$ 的话可以再构造呀，那是不是可以在开一个虚点呢？？

因为要求虚点点权为零，所以说我们这样子：新建两个虚点，一个点权为 $-1$ ，一个为 $1$ ，然后 $-1$ 连向上一个 $1$ 的虚点，所有新加的实点连到 $1$ ，每次断 $-1$ 和上一个 $1$ 的虚点连的边。

（好赖配个图嘛）

（没错就是长这样的）

这样子如果查询两个点在一个虚点下， $lca$ 必然是虚点 $1$ ，并且 $lca$ 的 $fa$ 点权是 $-1$ ；假如不在一个虚点下，同样也会跑到一个虚点 $1$ ，那这样路径和就定了，清楚了 lca 和 $lca$ 的 $fa$ ，那就不在乎树上父子关系了，硬上 $\text{LCT}$ 就可以了。

（PS：因为每次新节点都会长到生长节点的下面，所有的生长节点除了初始节点全都被建成了虚点，所以无论在哪里 $lca$ 始终会停在虚点（或者初始节点））

Code

/*

*/
#include 
using namespace std;
typedef long long ll;
const int N = 6e5 + 10, M = 8e5 + 10;
int n, m, tot, c1, c2, L[N], R[N], ans[N];
struct mdzz {
	int p, t, op, x, y;
	bool operator < (const mdzz &it) const {
		return (p == it.p) ? (t == it.t ? op > it.op : t < it.t) : p < it.p;
	}
} qu[M];
struct ios {
	inline char gc() {
		static const int IN_LEN = 1 << 18 | 1;
		static char buf[IN_LEN], *s, *t;
		return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
	}
	template  inline ios & operator >> (_Tp & x) {
		static char ch, sig; ch = gc(); sig = 0;
		for (; !isdigit(ch); ch = gc()) {if (ch == -1) return *this; sig |= (ch =='-');}
		for (x = 0; isdigit(ch); ch = gc()) x = (x << 3) + (x << 1) + (ch ^ 48);
		sig && (x = -x); return *this;
	}
} io;
inline double dead() {
	char ch = io.gc();
	ll s = 0, w = 1, k = 0;
	double m = 1; bool is = 0;
	while (!isdigit(ch)) {if (ch == '-') w = -1; ch = io.gc();}
	while (isdigit(ch) || ch == '.') {
		if (ch == '.') is = 1;
		else if (!is) s = (s << 3) + (s << 1) + (ch ^ 48);
		else k = (k << 3) + (k << 1) + (ch ^ 48), m *= 0.1;
		ch = io.gc();
	}
	return (m * k + s) * w;
}
inline string sead() {
	char ch = io.gc();
	string s;
	while (ch == ' ' || ch == '\n' || ch == '\t' || ch == '\r' || ch == EOF) ch = io.gc();
	while (ch != ' ' && ch != '\n' && ch != '\t' && ch != '\r' && ch != EOF) s += ch, ch = io.gc();
	return s;
}
struct LCT {
	#define ls(x) ch[x][0]
	#define rs(x) ch[x][1]
	int ch[N][2], fa[N], siz[N], rev[N], val[N], sta[N], top;
	inline bool pd(int x) {return rs(fa[x]) == x;}
	inline bool isrt(int x) {return ls(fa[x]) != x && rs(fa[x]) != x;}
	inline void pushup(int x) {siz[x] = siz[ls(x)] + val[x] + siz[rs(x)];}
	inline void pushdown(int x) {
		if (!rev[x]) return ;
		rev[ls(x)] ^= 1; rev[rs(x)] ^= 1; swap(ls(x), rs(x)); rev[x] = 0;
	}
	inline void rotate(int x) {
		int d = fa[x], t = pd(x);
		ch[d][t] = ch[x][t ^ 1]; fa[ch[x][t ^ 1]] = d;
		if (!isrt(d)) ch[fa[d]][pd(d)] = x;
		fa[x] = fa[d]; ch[x][t ^ 1] = d; fa[d] = x;
		pushup(d); pushup(x);
	}
	inline void update(int x) {
		for (; ; x = fa[x]) {sta[++top] = x; if (isrt(x)) break;}
		while (top) {pushdown(sta[top]); --top;}
	}
	inline void rotaup(int x) {rotate(pd(x) ^ pd(fa[x]) ? x : fa[x]); rotate(x);}
	inline void splay(int x) {
		update(x); for(; !isrt(fa[x]) && !isrt(x); rotaup(x));
		if (!isrt(x)) rotate(x);
	}
	inline int access(int x) {
		int y = 0;
		for (; x; y = x, x = fa[x]) {splay(x); rs(x) = y; pushup(x);}
		return y;
	}
	inline void makert(int x) {access(x); splay(x); rev[x] ^= 1;}
	inline void split(int x, int y) {makert(x); access(y); splay(y);}
	inline int findrt(int x) {
		access(x); splay(x);
		while (ls(x)) pushdown(x), x = ls(x);
		splay(x); return x;
	}
	inline void link(int x, int y) {makert(x); if (findrt(y) != x) fa[x] = y;}
	inline void cut(int x, int y) {
		if (findrt(x) != findrt(y)) return ;
		split(x, y);
		if(fa[x] != y || rs(x)) return ;
		fa[x] = ls(y) = 0; pushup(x);
	}
	inline int query(int x, int y) {
		int ans = 0, lca;
		access(x); splay(x); ans = siz[x];
		lca = access(y); splay(y); ans += siz[y];
		access(lca); splay(lca); ans -= (siz[lca] << 1);
		return ans;
	}
	#undef ls
	#undef rs
} lct;
int main() {
//	freopen("forest.in", "r", stdin);
//	freopen("forest.out", "w", stdout);
	io >> n >> m; c1 = 1; c2 = m;
	lct.val[1] = 1; L[1] = 1; R[1] = n;
	++c2; lct.val[c2] = -1, lct.link(c2, 1);
	++c2; lct.val[c2] = 1, lct.link(c2, c2 - 1);
	memset(ans, -1, sizeof(ans));
	for (int i = 1, op, l, r, x; i <= m; ++i) {
		io >> op;
		if (op == 2) {io >> x >> l >> r; qu[++tot] = (mdzz) {x, i, 2, l, r};}
		else if (!op) {
			++c1, lct.val[c1] = 1, lct.link(c1, c2); io >> L[c1] >> R[c1];
		}
		else {
			io >> l >> r >> x; l = max(l, L[x]); r = min(r, R[x]);
			if (l > r) continue;
			++c2; lct.val[c2] = -1, lct.link(c2, c2 - 1);
			++c2; lct.val[c2] = 1, lct.link(c2, c2 - 1);
			qu[++tot] = (mdzz) {l, i, 1, c2 - 1, c2 - 2};
			qu[++tot] = (mdzz) {l, i, 0, c2 - 1, x};
			qu[++tot] = (mdzz) {r + 1, i, 1, c2 - 1, x};
			qu[++tot] = (mdzz) {r + 1, i, 0, c2 - 1, c2 - 2};
		}
	}
	sort(qu + 1, qu + 1 + tot);
	for (int i = 1; i <= tot; ++i) {
		if (!qu[i].op) lct.link(qu[i].x, qu[i].y);
		else if (qu[i].op == 1) lct.cut(qu[i].x, qu[i].y);
		else ans[qu[i].t] = lct.query(qu[i].x, qu[i].y);
	}
	for (int i = 1; i <= m; ++i) if (~ans[i]) printf("%d\n", ans[i]);
	return 0;
}

这篇关于[ZJOI2016]大森林的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程