Description

现在有 \(n\) 棵以 \(1\) 为根的树，每棵树有一个生长节点，有 \(m\) 次操作，每次操作是下面三种中的一个：

在 \(l\sim r\) 的这些树的生长节点下面增加一个新的节点
将 \(l\sim r\) 的生长节点都变为 \(x\)
查询第 \(x\) 棵树种 \(u\sim v\) 的距离

\(n\le 10^5,m\le 2\times 10^5\)

Solution

我们可以发现的是，我们加点或者增加新节点并不会改变已有查询的答案，也就是说，我们是可以离线的。另外，我们可以发现，增加多的点并不会有什么影响，也就是说，我们第一个操作就没有什么意义了，可以大家一起加。

考虑操作 \(2\)，可以想到的是，假如我们的生长节点是 \(x_1\to x_2\)，那么，其实我们也可以理解为生长节点不变，在查询的时候，把更改后这段时间中增加的节点都加到 \(x_2\) 来。于是，我们就需要实现类似于子树转移的东西，这个可以新建一个虚点，所有点都连到虚点上，直接虚点改变父亲就好了。

对于查询而言，我们肯定是离线下来。因为每次操作都是区间操作，所以我们可以用类似于差分的方法来一棵一颗的统计。我们可以先处理出来每次要在哪里把那个子树转移到哪里。对于操作 \(2\) 来说，就可以变为在 \(l\) 处把上一次操作 \(2\) 到此次操作 \(2\) 之间加入的点的子树都转移到 \(x_2\)，然后在 \(r+1\) 又转移到 \(x_1\)。

于是，问题就是如何查询一棵树上两个点之间的距离了。我们可以直接用 \(\text{access}\) 求到两个点的 \(\text{lca}\) 然后差分一波就好了。

时间复杂度 \(\Theta((n+m)\log n)\)。

Code

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define MAXN 300005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,cnt,fuc,las,tot,qL[MAXN],qR[MAXN],ans[MAXN],ind[MAXN],sum[MAXN],val[MAXN],par[MAXN],son[MAXN][2];

bool rnk (int x){return son[par[x]][1] == x;}

bool Isroot (int x){return son[par[x]][0] != x && son[par[x]][1] != x;}

void Pushup (int x){sum[x] = sum[son[x][0]] + sum[son[x][1]] + val[x];}

void newnode (int v){++ cnt,val[cnt] = sum[cnt] = v;}

void rotate (int x){

	int y = par[x],z = par[y],k = rnk (x),w = son[x][!k];

	if (!Isroot (y)) son[z][rnk (y)] = x;son[x][!k] = y,son[y][rnk (x)] = w;

	if (w) par[w] = y;par[x] = z,par[y] = x;

	Pushup (y),Pushup (x);

}

void Splay (int x){

	while (!Isroot (x)){

		int y = par[x];

		if (!Isroot (y)) rotate (rnk (x) == rnk (y) ? y : x);

		rotate (x);

	}

}

int Access (int x){int y;for (y = 0;x;x = par[y = x]) Splay (x),son[x][1] = y,Pushup (x);return y; }

int getans (int x,int y){

	int ans = 0,s;Access (x),Splay (x),ans += sum[x],s = Access (y),Splay (y),ans += sum[y],Access (s),Splay (s),ans -= 2 * sum[s];

	return ans;

}

void link (int x,int y){Splay (x),par[x] = y;}

void cut (int x){Access (x),Splay (x),par[son[x][0]] = 0,son[x][0] = 0;Pushup (x);}

struct node{

	int pos,tim,x,y;

	bool operator < (const node &p)const{return pos != p.pos ? pos < p.pos : tim < p.tim;}

}q[MAXN];

signed main(){

	read (n,m);newnode (1),qL[1] = 1,qR[1] = n,las = ind[fuc = 1] = 1;int qn = 0;

	for (Int i = 1;i <= m;++ i){

		int opt,x,y;read (opt,x,y);

		if (opt == 0) ++ fuc,newnode (1),ind[fuc] = cnt,qL[fuc] = x,qR[fuc] = y,q[++ tot] = node {1,i - m,cnt,las};

		else if (opt == 1){

			int k;read (k);

			x = max (x,qL[k]),y = min (y,qR[k]);

			if (x <= y) newnode (0),link (cnt,las),q[++ tot] = node {x,i - m,cnt,ind[k]},q[++ tot] = node {y + 1,i - m,cnt,las},las = cnt;

		}

		else{

			int k;read (k);

			q[++ tot] = node {x,++ qn,ind[y],ind[k]};

		}

	}

	sort (q + 1,q + tot + 1),memset (ans,-1,sizeof (ans));

	for (Int i = 1,j = 1;i <= n;++ i)

		for (;q[j].pos == i;++ j){

			if (q[j].tim <= 0) cut (q[j].x),link (q[j].x,q[j].y);

			else ans[q[j].tim] = getans (q[j].x,q[j].y);

		}

	for (Int i = 1;i <= qn;++ i) write (ans[i]),putchar ('\n');

 	return 0;

}

巴特西

题解 [ZJOI2016]大森林

Description

Solution

Code

最新文章

热门文章