OI

BZOJ 2243 染色

Description

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面 行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

1
2
3

3
1
2

HINT

N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

Solution

这道题其实不算太难，但是毕竟我是10天没写代码了，写起来手生，上来getcolor写错了…return的是线段树中的id而不是我们找的pos… QAQ

还有一个错误出错在初始化，错误代码WA，目前还不知道怎么WA的，然后我用for遍历挨个change一下结果就A了，常数太大了，7372ms… VerySlow

大体思路就是记录每个线段树中的ans，左右断点颜色，还有是否被某种颜色覆盖。

对于每次询问的时候的细节 有两种做法 一种是找这次的和下次的 还有种是找这次的和上次的（颜色是不是一样），一样的话答案减去1.

思路就这样吧…胡乱搞搞就好了…

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

#include <cstdio>
const int maxn = 100005;
int getint() {
	int r = 0; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar());
	for (;  '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r;
}
char getop() {
	char c;
	for (c = getchar(); c != 'Q' && c != 'C'; c = getchar());
	return c;
}
void swap(int &x, int &y) { int tmp = x; x = y; y = tmp; }
int lc[maxn << 2], rc[maxn << 2], cov[maxn << 2], ans[maxn << 2];
int n, m, cnte = 0, dfs_index = 0;
int h[maxn], c[maxn], top[maxn], dep[maxn], fat[maxn], son[maxn], siz[maxn], tid[maxn];
struct edge_type { int v, next; } edge[maxn << 1];
void ins(int u, int v) {
	edge[++cnte].v = v;
	edge[cnte].next = h[u];
	h[u] = cnte;
}
void push_down(int now, int l, int r) {
	if (cov[now] == -1 || l == r) return;
	lc[now << 1] = rc[now << 1] = cov[now << 1] = lc[now << 1 | 1] = rc[now << 1 | 1] = cov[now << 1 | 1] = cov[now];
	ans[now << 1] = ans[now << 1 | 1] = 1;
	cov[now] = -1;
	return;
}

void push_up(int now, int l, int r) {
	if (l == r) return;
	lc[now] = lc[now << 1];
	rc[now] = rc[now << 1 | 1];
	ans[now] = ans[now << 1] + ans[now << 1 | 1];
	if (rc[now << 1] == lc[now << 1 | 1]) --ans[now];
}

void dfs1(int now, int father, int deep) {
	fat[now] = father; dep[now] = deep; siz[now] = 1; son[now] = 0;
	int v;
	for (int i = h[now]; i; i = edge[i].next) {
		v = edge[i].v;
		if (father == v) continue;
		dfs1(v, now, deep + 1);
		siz[now] += siz[v];
		if (siz[son[now]] < siz[v]) son[now] = v;
	}
}
void dfs2(int now, int father, int tp) {
	++dfs_index; top[now] = tp; tid[now] = dfs_index;
	if (son[now]) {
		dfs2(son[now], now, tp);
		int v;
		for (int i = h[now]; i; i = edge[i].next) {
			v = edge[i].v;
			if (v == father || v == son[now]) continue;
			dfs2(v, now, v);
		}
	}
}
void build_tree(int now, int l, int r) {
	cov[now] = -1;
	ans[now] = 1;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build_tree(now << 1, l, mid);
	build_tree(now << 1 | 1, mid + 1, r);
	return;
}
void change_tree(int now, int ll, int rr, int l, int r, int col) {
	push_down(now, l, r);
	if (ll <= l && r <= rr) {
		lc[now] = rc[now] = cov[now] = col;
		ans[now] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (ll <= mid) change_tree(now << 1, ll, rr, l, mid, col);
	if (rr > mid) change_tree(now << 1 | 1, ll, rr, mid + 1, r, col);
	push_up(now, l, r);
	return;
}
int query_tree(int now, int ll, int rr, int l, int r) {
	push_down(now, l, r);
	if (ll <= l && r <= rr) return ans[now];
	int mid = (l + r) >> 1, ret = 0;
	if (ll <= mid) ret += query_tree(now << 1, ll, rr, l, mid);
	if (rr > mid) ret += query_tree(now << 1 | 1, ll, rr, mid + 1, r);
	if (ll <= mid && rr > mid && rc[now << 1] == lc[now << 1 | 1]) --ret;
	return ret;
}
void init() {
	n = getint(); m = getint();
	int u, v;
	for (int i = 1; i <= n; ++i) c[i] = getint();
	for (int i = 1; i < n; ++i) {
		u = getint();
		v = getint();
		ins(u, v);
		ins(v, u);
	}
	dfs1(1, 0, 1);
	dfs2(1, 0, 1);
	build_tree(1, 1, n);
	for (int i = 1; i <= n; ++i) change_tree(1, tid[i], tid[i], 1, n, c[i]);
}
void change(int u, int l, int col) {
	while (top[u] != top[l]) {
		change_tree(1, tid[top[u]], tid[u], 1, n, col);
		u = fat[top[u]];
	}
	change_tree(1, tid[l], tid[u], 1, n, col);
}
int gc(int now, int l, int r, int pos) {
	push_down(now, l, r);
	if (l == r) return lc[now];
	int mid = (l + r) >> 1;
	if (pos <= mid) return gc(now << 1, l, mid, pos);
	else return gc(now << 1 | 1, mid + 1, r, pos);
}
int query(int u, int l) {
	int ret = 0;
	while (top[u] != top[l]) {
		ret += query_tree(1, tid[top[u]], tid[u], 1, n);
		if (gc(1, 1, n, tid[top[u]]) == gc(1, 1, n, tid[fat[top[u]]])) --ret;
		u = fat[top[u]];
	}
	ret += query_tree(1, tid[l], tid[u], 1, n);
	return ret;
}
int lca(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fat[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	return u;
}
void work() {
	char op;
	int x, y, z, l;
	while (m--) {
		op = getop();
		if (op == 'C') {
			x = getint(); y = getint(); z = getint();
			l = lca(x, y);
			change(x, l, z);
			change(y, l, z);
		} else {
			x = getint(); y = getint();
			l = lca(x, y);
			printf("%d\n", query(x, l) + query(y, l) - 1);
		}
	}
}
int main() {
	init();
	work();
	return 0;
}