[SDOI2011]染色 题解
题目地址:洛谷:【P2486】[SDOI2011]染色 – 洛谷、BZOJ:Problem 2243. — [SDOI2011]染色
题目描述
给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),
如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
输入输出格式
输入格式:
第一行包含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)路径上的颜色段数量。
输出格式:
对于每个询问操作,输出一行答案。
输入输出样例
输入样例#1:
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
输出样例#1:
3 1 2
说明
数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间。
题解
树链信息自然就是树剖。线段树维护当前区间左右端颜色以及这段区间中间有几段。合并检查拼接点是否同样颜色。树剖上跳的过程类似,实现见代码。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline bool isop(char c) {
return c == 'Q' || c == 'C';
}
inline char readop() {
char c;
while(!isop(c = fgc()));
return c;
}
const int MAXN = 100005;
int n, m, w[MAXN], ut, vt, at, bt, ct;
char op;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];
inline void addedge(int u, int v) {
gra[u].push_back(v);
gra[v].push_back(u);
}
inline void dfs1(int u) {
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
siz[u] += siz[v] + 1;
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++cnt;
ptn[dfn[u]] = u;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
struct Node {
int l, r, tot;
bool tag;
} sgt[MAXN << 2];
inline void pushdown(int o, int l, int r) {
int lch = o << 1, rch = (o << 1) | 1;
if(sgt[o].tag) {
sgt[lch].l = sgt[lch].r = sgt[rch].l = sgt[rch].r = sgt[o].l;
sgt[lch].tag = sgt[rch].tag = true;
sgt[lch].tot = sgt[rch].tot = 1;
sgt[o].tag = false;
}
}
inline void merge(Node &rt, Node ls, Node rs) {
rt.l = ls.l;
rt.r = rs.r;
rt.tot = ls.tot + rs.tot;
if(ls.r == rs.l) rt.tot--;
}
inline void build(int o, int l, int r) {
if(l == r) {
sgt[o].l = sgt[o].r = w[ptn[l]];
sgt[o].tot = 1;
return;
}
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
build(lch, l, mid);
build(rch, mid + 1, r);
merge(sgt[o], sgt[lch], sgt[rch]);
}
inline void modify(int o, int l, int r, int ll, int rr, int v) {
if(l == ll && r == rr) {
sgt[o].l = sgt[o].r = v;
sgt[o].tot = 1;
sgt[o].tag = true;
return;
}
pushdown(o, l, r);
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(rr <= mid) {
modify(lch, l, mid, ll, rr, v);
} else if(ll > mid) {
modify(rch, mid + 1, r, ll, rr, v);
} else {
modify(lch, l, mid, ll, mid, v);
modify(rch, mid + 1, r, mid + 1, rr, v);
}
merge(sgt[o], sgt[lch], sgt[rch]);
}
inline Node query(int o, int l, int r, int ll, int rr) {
if(l == ll && r == rr) {
return sgt[o];
}
pushdown(o, l, r);
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(rr <= mid) {
return query(lch, l, mid, ll, rr);
} else if(ll > mid) {
return query(rch, mid + 1, r, ll, rr);
} else {
Node ls = query(lch, l, mid, ll, mid), rs = query(rch, mid + 1, r, mid + 1, rr), res;
merge(res, ls, rs);
return res;
}
}
inline void modify(int u, int v, int c) {
int tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] > dep[tv]) {
std::swap(tu, tv);
std::swap(u, v);
}
modify(1, 1, n, dfn[tv], dfn[v], c);
v = fa[tv];
tv = top[v];
}
if(dep[u] > dep[v]) std::swap(u, v);
modify(1, 1, n, dfn[u], dfn[v], c);
}
inline int query(int u, int v) {
Node t;
int res = 0, cu = -1, cv = -1, tu = top[u], tv = top[v];
while(tu != tv) {
if(dep[tu] > dep[tv]) {
std::swap(tu, tv);
std::swap(u, v);
std::swap(cu, cv);
}
t = query(1, 1, n, dfn[tv], dfn[v]);
res += t.tot;
if(t.r == cv) res--;
cv = t.l;
v = fa[tv];
tv = top[v];
}
if(dep[u] > dep[v]) {
std::swap(u, v);
std::swap(cu, cv);
}
t = query(1, 1, n, dfn[u], dfn[v]);
res += t.tot;
if(t.l == cu) res--;
if(t.r == cv) res--;
return res;
}
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) w[i] = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint();
addedge(ut, vt);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
while(m--) {
op = readop();
at = readint();
bt = readint();
if(op == 'Q') {
printf("%d\n", query(at, bt));
}
if(op == 'C') {
ct = readint();
modify(at, bt, ct);
}
}
return 0;
}