【BZOJ 4530】[BJOI2014] 大融合

相关链接

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

解题报告

这题LCT是可以做的

但因为本题没有要求强制在线
所以我们可以用并查集来维护连通性,再用线段树合并来支持支持DFS序的区间询问
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

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 void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

【BZOJ 3551】[ONTAK2010] Peaks加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3551
神犇题解:http://blog.csdn.net/popoqqq/article/details/41348785

解题报告

这题强制在线,所以不能直接上启发式合并
或者强行可持久化也可以?
不过我们有更加优美的东西:Kruskal重构树

就是按照边权排序,然后做Kruskal
如果需要加边,那么我们新建一个结点,权值设为这条边的权值
然后把原来的两个点连到这个点下面当儿子
于是任意两点之间的最大边权就是他们的LCA的权值了

对于原题来讲,我们可以先倍增到最浅的可以到达的祖先
那么这个祖先的子树就是可以到达的所有点了
考虑DFS序,问题变为区间k大,这是主席树的经典应用
于是这题就做完啦!

今天上午考试考了一道类似的题目,然而忘了这个做法
是用的线段树合并+标记永久化,虽然能A但显然不如这个优雅

【Codeforces 741D】Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

相关链接

题目传送门:http://codeforces.com/contest/741/problem/D
中文题面:https://blog.sengxian.com/solutions/cf-741d

解题报告

看起来这个串的定义非常强的样子,但仔细观察不难发现,就是出现次数为奇数的字母最多出现一个
于是我们定时一个二进制状态$f_{i,j}$表示$i$到$j$这段路径中哪些字符出现了奇数次

我们考虑在每一条合法路径的LCA处将其统计
于是就变成了子树相关问题,于是非常自然想到启发式合并

考虑从子树最大的儿子那里继承集合,其他的儿子的集合暴力加入
因为走一条边,需要异或一个值,整个集合的转移我们可以记录一个标记,然后在插入时使其生效
考虑统计的话,我们在暴力插入的时候,枚举是哪一位不同,单次查询是$O(22)$的
又因为加入是$O(1)$的,所以总的时间复杂度$O(n \log n \cdot 22)$

【BZOJ 4771】七彩树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4771
数据生成器:http://paste.ubuntu.com/24181811/
神犇题解:https://blog.sengxian.com/solutions/bzoj-4771

解题报告

这题sengxian又写了题解了,我又不想写了…..
不过,还是XJB说一说吧!题还是很好的

就是搞两类线段树,两类线段树都支持合并
其中一类线段树,下标是颜色的编号,叶子结点记录的是该种颜色的最浅深度,这个是用来更新第二类线段树的
另一类线段树的下标是深度,结点记录的是区间和,这个是用来回答询问的
我们先把第二类线段树给Merge起来,不过我们发现同一种颜色可能会算重
不过我们也可以发现,再Merge第一类线段树的时候,如果叶子结点重了
那么在第一类线段树里减掉深度较深的那个点之后,答案就没有问题了

另外的话,因为这题强制在线
于是我们还需要把第一类线段树给可持久化
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 200009;
const int M = 1e7;

int n,m,head[N],to[N],nxt[N],dep[N],col[N],fa[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 Segment_Tree_Sum{
	int cnt,AnsTmp,root[N],ch[M][2],sum[M]; 
	public:
		inline void modify(int w, int p, int delta) {
			modify(root[w], 1, n, p, delta); 
		}
		inline void merge(int a, int b) {
			root[a] = Merge(root[a], root[b]); 
		}
		inline int query(int w, int d) {
			AnsTmp = 0;
			query(root[w], 1, n, 1, d);
			return AnsTmp;
		}
		inline void init() {
			memset(root,0,sizeof(int)*(n+5));
			memset(ch,0,sizeof(int)*(cnt+5)*2);
			memset(sum,0,sizeof(int)*(cnt+5));
			cnt = 0;
		}
	private:
		void modify(int &w, int l, int r, int p, int delta) {
			w = cpy(w); sum[w] += delta;
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) modify(ch[w][0], l, mid-1, p, delta);
				else modify(ch[w][1], mid, r, p, delta);
			}
		}
		int Merge(int a, int b) {
			a = a? cpy(a): 0; b = b? cpy(b): 0; 
			if (!b || !a) return a + b;
			else {
				if (ch[a][0] || ch[a][1]) {
					ch[a][0] = Merge(ch[a][0], ch[b][0]);
					ch[a][1] = Merge(ch[a][1], ch[b][1]);
				}
				return sum[a] += sum[b], a;
			}
		}
		void query(int w, int l, int r, int L, int R) {
			if (L <= l && r <= R) AnsTmp += sum[w];
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R);
				if (mid <= R) query(ch[w][1], mid, r, L, R);
			}
		}
		inline int cpy(int b) {
			memcpy(ch[++cnt], ch[b], 8);
			sum[cnt] = sum[b]; return cnt;
		}	
}STS;

class Segment_Tree_Col{
	int cnt,root[N],ch[M][2],mn[M];
	public:
		inline void insert(int w, int c) {
			insert(root[w], 1, n, c, dep[w]);
			STS.modify(w, dep[w], 1);
		}
		inline void merge(int a, int b) {
			STS.merge(a, b);
			root[a] = merge(root[a], root[b], a);
		}
		inline void init() {
			memset(root,0,sizeof(int)*(n+5));
			memset(ch,0,sizeof(int)*(cnt+5)*2);
			memset(mn,0,sizeof(int)*(cnt+5));
			cnt = 0;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++cnt; if (l == r) mn[w] = v;
			else {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}	
		}
		int merge(int a, int b, int w) {
			if (!a || !b) return a + b;
			else if (ch[a][0] || ch[a][1]) {
				ch[a][0] = merge(ch[a][0], ch[b][0], w);
				ch[a][1] = merge(ch[a][1], ch[b][1], w);
			} else {
				STS.modify(w, max(mn[a], mn[b]), -1);
				mn[a] = min(mn[a], mn[b]);
			} return a;
		}
}STC;

int main() {
	for (int T=read();T;T--) {
		n = read(); m = read();
		STS.init(); STC.init(); dep[1] = 1;
		for (int i=1;i<=n;i++) col[i] = read();
		for (int i=2;i<=n;i++) dep[i] = dep[fa[i]=read()] + 1;
		for (int i=1;i<=n;i++) STC.insert(i, col[i]); 
		for (int i=n;i>1;i--) STC.merge(fa[i], i);
		for (int i=1,x,d,last=0;i<=m;i++) {
			x = read() ^ last; d = read() ^ last;
			printf("%d\n",last=STS.query(x, dep[x]+d));
		} 
	}
	return 0;
}

—————————— UPD 2017.4.11 ——————————
似乎Clairs之前出过这个题了…….
http://www.cnblogs.com/clrs97/p/5538804.html