【BZOJ 4817】[SDOI2017] 树点涂色

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817

解题报告

我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数

于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$

Code

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

const int N = 100009;
const int M = N << 1;
const int LOG = 20;

int n, m, head[N], nxt[M], to[M]; 
int in[N], ot[N], dep[N], num[N], ff[N][LOG];

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

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LOG - 1; ~j; j--) {
		if (dep[ff[u][j]] >= dep[v]) {
			u = ff[u][j];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LOG - 1; ~j; j--) {
		if (ff[u][j] != ff[v][j]) {
			u = ff[u][j];
			v = ff[v][j];
		}
	}
	return ff[u][0];
}

class SegmentTree{
	int root, ch[M][2], tag[M], mx[M];
public:
	inline void init() {
		build(root, 1, n);
	}
	inline void modify(int l, int r, int d) {
		modify(root, 1, n, l, r, d);
	}
	inline int query(int l, int r = -1) {
		return query(root, 1, n, l, r >= 0? r: l);
	}
private:
	inline void PushDown(int w) {
		if (tag[w]) {
			int ls = ch[w][0], rs = ch[w][1];
			mx[ls] += tag[w];
			mx[rs] += tag[w];
			tag[ls] += tag[w];
			tag[rs] += tag[w];
			tag[w] = 0;
		}
	}
	inline int query(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return mx[w];
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) {
				ret = max(ret, query(ch[w][0], l, mid - 1, L, R));
			}
			if (mid <= R) {
				ret = max(ret, query(ch[w][1], mid, r, L, R));
			}
			return ret;
		}
	}
	inline void modify(int w, int l, int r, int L, int R, int d) {
		if (L <= l && r <= R) {
			tag[w] += d;
			mx[w] += d;
		} else {
			PushDown(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) {
				modify(ch[w][0], l, mid - 1, L, R, d);
			}
			if (mid <= R) {
				modify(ch[w][1], mid, r, L, R, d);
			}
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
	inline void build(int &w, int l, int r) {
		static int cnt = 0;
		w = ++cnt;
		if (l == r) {
			mx[w] = dep[num[l]];
		} else {
			int mid = l + r + 1 >> 1;
			build(ch[w][0], l, mid - 1);
			build(ch[w][1], mid, r);
			mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);
		}
	}
}SGT;

class LinkCutTree{
	int ch[N][2], fa[N];
public:
	inline void SetFather(int w, int f) {
		fa[w] = f;
	}
	inline void access(int x) {
		for (int last = 0; x; last = x, x = fa[x]) {
			splay(x);
			if (fa[x]) {
				int p = GetMin(x);
				SGT.modify(in[p], ot[p], -1);
			}
			if (ch[x][1]) {
				int p = GetMin(ch[x][1]);
				SGT.modify(in[p], ot[p], 1);
			}
			ch[x][1] = last;
		}
	}
private:
	inline bool IsRoot(int x) {
		return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x);
	}
	inline int GetMin(int x) {
		return ch[x][0]? GetMin(ch[x][0]): x;
	}
	inline void splay(int x) {
		for (int f, ff; !IsRoot(x); ) {
			f = fa[x], ff = fa[f];
			if (IsRoot(f)) {
				rotate(x);
			} else {
				if ((ch[ff][0] == f) ^ (ch[f][0] == x)) {
					rotate(x);
					rotate(x);
				} else {
					rotate(f);
					rotate(x);
				}
			}
		}
	}
	inline void rotate(int x) {
		int f = fa[x], t = ch[f][1] == x;
		fa[x] = fa[f];
		if (!IsRoot(f)) {
			ch[fa[f]][ch[fa[f]][1] == f] = x;
		}
		ch[f][t] = ch[x][t ^ 1];
		fa[ch[x][t ^ 1]] = f;
		ch[x][t ^ 1] = f;
		fa[f] = x;
	}
}LCT;

inline void DFS(int w, int f) {
	static int ID = 0;
	LCT.SetFather(w, f);
	ff[w][0] = f;
	dep[w] = dep[f] + 1;
	num[in[w] = ++ID] = w;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	ot[w] = ID;
}	

int main() {
	n = read(); m = read();
	for (int i = 1; i < n; i++) {
		AddEdge(read(), read());
	}
	DFS(1, 0);
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= n; i++) {
			ff[i][j] = ff[ff[i][j - 1]][j - 1];
		}
	}
	SGT.init();
	for (int i = 1; i <= m; i++) {
		int opt = read();
		if (opt == 1) {
			LCT.access(read());
		} else if (opt == 2) {
			int u = read(), v = read(), lca = LCA(u, v);
			printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1);
		} else {
			int x = read();
			printf("%d\n", SGT.query(in[x], ot[x]));
		}
	}
	return 0;
}

【BZOJ 3514】Codechef MARCH14 GERALD07加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3514
神犇题解:http://www.cnblogs.com/zhonghaoxi/p/3651591.html

解题报告

这是LCT的经典应用,我们把每条边的权值设为它的编号
然后用LCT动态维护最大生成树
同时记录第$i$条边加入时取代的那一条边的编号$a_i$

对于询问,我们发现对于询问$[l,r]$
只有$a_i < l$的边才会使连通块的大小减少$1$
于是问题变为询问一个区间内小于某个数的个数
这是又是函数式线段树的经典应用

于是这题用LCT和函数式线段树就可以解决
时间复杂度:$O(n \log n)$

相关拓展

这题还可以很方便地将问题改为删掉$[l,r]$的边之后连通块的个数
这个我们将序列倍长,然后直接转化为原问题

【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;
}

【日常小测】String

题目大意

先给定一个长度为$n(n \le 50000)$的字符串$S$
之后给定$m(m \le 50000)$个操作(强制在线),操作分两种

  1. 在字符串$S$末尾加入一个字符
  2. 将$S$的子串$[l,r]$取出来,设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

解题报告

我们考虑用一棵线段树来支持插入斜率为$-1$的线段,并询问区间最值
这个是用来维护答案的,至于为什么插入的是线段,待会儿再说
至于具体实现,因为斜率相同,所以我们只需要将直线的纵截距插入即可,换言之我们只需要支持区间取$\max$即可

现在假设我们已经在维护了$[1,r-1]$的答案,并且我们在维护$[1,r]$回答所有右端点为$r$的询问
考虑插入第$r$个字符会影响哪些部分的答案:显然只会影响$fail$链上的答案
我们记录$last_x$表示$SAM$上的结点x代表的串在$S$中出现的最后一次的时间
我们注意到一条$fail$链上$last_x$一定是相等的,所以我们只需要考虑最长长度$l$
于是我们需要在线段树的$[last_x-l+1,last_x]$区间插入$x+y-(last_x+1)=0$的直线
之后我们更新$fail$链上的$last_x$,至于询问我们只需要到线段树上查询区间最值
当然维护$fail$树的话,我们需要使用$LCT$。

注意到$LCT$的一个$splay$里的$last_x$相等,所以单次$access$只会贡献$\log n$次区间取$\max$操作
所以我们已经能在$O(n \log ^2 n)$的时间复杂度内解决离线版本了
现在考虑在线版本,我们将线段树可持久化即可