2243: [SDOI2011]染色

Time Limit:?20 Sec??Memory Limit:?512 MB
Submit:?7971??Solved:?2990
[Submit][Status][Discuss]

Description

?

給定一棵有n個節(jié)點(diǎn)的無根樹和m個操作，操作有2類：

1、將節(jié)點(diǎn)a到節(jié)點(diǎn)b路徑上所有點(diǎn)都染成顏色c；

2、詢問節(jié)點(diǎn)a到節(jié)點(diǎn)b路徑上的顏色段數(shù)量（連續(xù)相同顏色被認(rèn)為是同一段），如“112221”由3段組成：“11”、“222”和“1”。

請你寫一個程序依次完成這m個操作。

?

Input

第一行包含2個整數(shù)n和m，分別表示節(jié)點(diǎn)數(shù)和操作數(shù)；

第二行包含n個正整數(shù)表示n個節(jié)點(diǎn)的初始顏色

下面?行每行包含兩個整數(shù)x和y，表示x和y之間有一條無向邊。

下面?行每行描述一個操作：

“C a b c”表示這是一個染色操作，把節(jié)點(diǎn)a到節(jié)點(diǎn)b路徑上所有點(diǎn)（包括a和b）都染成顏色c；

“Q a b”表示這是一個詢問操作，詢問節(jié)點(diǎn)a到節(jié)點(diǎn)b（包括a和b）路徑上的顏色段數(shù)量。

?

Output

對于每個詢問操作，輸出一行答案。

?

Sample Input

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

3

1

2

HINT

?

數(shù)N<=10^5，操作數(shù)M<=10^5，所有的顏色C為整數(shù)且在[0, 10^9]之間。

?

?

題目鏈接：BZOJ 2243

做了幾道普通的樹鏈剖分維護(hù)邊權(quán)、點(diǎn)權(quán)，查詢路徑的題目，感覺并沒有什么特點(diǎn)，然而這題比較有意思，求路徑上連續(xù)顏色有幾段，顯然用線段樹的話只要維護(hù)當(dāng)前區(qū)間最左和最右的顏色，左右子區(qū)間即可推出父區(qū)間的答案：左邊段數(shù)+右邊段數(shù)-（左區(qū)間右端點(diǎn)顏色==右區(qū)間左端點(diǎn)顏色）。然后統(tǒng)計的時候也要利用這個思想——線段樹的query與樹鏈剖分中記錄u與v上升區(qū)間段數(shù)的同時也與u、v最后上升的區(qū)間最左端點(diǎn)顏色比較得到答案。

代碼：

#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LC(x) (x<<1) #define RC(x) ((x<<1)+1) #define MID(x,y) ((x+y)>>1) #define fin(name) freopen(name,"r",stdin) #define fout(name) freopen(name,"w",stdout) #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define FAST_IO ios::sync_with_stdio(false);cin.tie(0); typedef pair<int, int> pii; typedef long long LL; const double PI = acos(-1.0); const int N = 100010; struct seg {int l, mid, r;int lc, rc;int s, tag; }; struct edge {int to, nxt;edge() {}edge(int _to, int _nxt): to(_to), nxt(_nxt) {} }; edge E[N << 1]; seg T[N << 2]; int head[N], tot; int sz[N], fa[N], son[N], top[N], dep[N], idx[N], ts; int arr[N]; int Rc, Lc;void init() {CLR(head, -1);tot = 0;ts = 0; } void add(int s, int t) {E[tot] = edge(t, head[s]);head[s] = tot++; } void dfs1(int u, int f, int d) {sz[u] = 1;fa[u] = f;son[u] = -1;dep[u] = d;for (int i = head[u]; ~i; i = E[i].nxt){int v = E[i].to;if (v != f){dfs1(v, u, d + 1);sz[u] += sz[v];if (son[u] == -1 || sz[son[u]] < sz[v])son[u] = v;}} } void dfs2(int u, int tp) {idx[u] = ++ts;top[u] = tp;if (~son[u])dfs2(son[u], tp);for (int i = head[u]; ~i; i = E[i].nxt){int v = E[i].to;if (v != fa[u] && v != son[u])dfs2(v, v);} } void pushup(int k) {T[k].s = T[LC(k)].s + T[RC(k)].s - (T[LC(k)].rc == T[RC(k)].lc);T[k].lc = T[LC(k)].lc;T[k].rc = T[RC(k)].rc; } void pushdown(int k) {if (T[k].tag == -1)return ;T[LC(k)].tag = T[RC(k)].tag = T[k].tag;T[LC(k)].lc = T[LC(k)].rc = T[k].tag;T[RC(k)].lc = T[RC(k)].rc = T[k].tag;T[LC(k)].s = T[RC(k)].s = 1;T[k].tag = -1; } void build(int k, int l, int r) {T[k].l = l;T[k].r = r;T[k].mid = MID(l, r);T[k].lc = T[k].rc = 0;T[k].tag = -1;T[k].s = 0;if (l == r)return ;build(LC(k), l, T[k].mid);build(RC(k), T[k].mid + 1, r); } void update(int k, int l, int r, int c) {if (l <= T[k].l && T[k].r <= r){T[k].tag = c;T[k].lc = T[k].rc = c;T[k].s = 1;}else{pushdown(k);if (r <= T[k].mid)update(LC(k), l, r, c);else if (l > T[k].mid)update(RC(k), l, r, c);else{update(LC(k), l, T[k].mid, c);update(RC(k), T[k].mid + 1, r, c);}pushup(k);} } int query(int k, int l, int r, int L, int R) {if (L == T[k].l)Lc = T[k].lc;if (R == T[k].r)Rc = T[k].rc;if (l <= T[k].l && T[k].r <= r)return T[k].s;else{pushdown(k);if (r <= T[k].mid)return query(LC(k), l, r, L, R);else if (l > T[k].mid)return query(RC(k), l, r, L, R);elsereturn query(LC(k), l, T[k].mid, L, R) + query(RC(k), T[k].mid + 1, r, L, R) - (T[LC(k)].rc == T[RC(k)].lc);} } int Find(int u, int v) {int ret = 0;int tu = top[u], tv = top[v];int last_u = -1, last_v = -1;while (tu != tv){if (dep[tu] < dep[tv]){swap(tu, tv);swap(u, v);swap(last_u, last_v);}ret += query(1, idx[tu], idx[u], idx[tu], idx[u]);if (Rc == last_u)--ret;last_u = Lc;u = fa[tu];tu = top[u];}if (dep[u] > dep[v]){swap(u, v);swap(last_u, last_v);}ret += query(1, idx[u], idx[v], idx[u], idx[v]);if (Lc == last_u)--ret;if (Rc == last_v)--ret;return ret; } void solve(int u, int v, int c) {int tu = top[u], tv = top[v];while (tu != tv){if (dep[tu] < dep[tv]){swap(tu, tv);swap(u, v);}update(1, idx[tu], idx[u], c);u = fa[tu];tu = top[u];}if (dep[u] > dep[v])swap(u, v);update(1, idx[u], idx[v], c); } int main(void) {int n, m, a, b, c, i;char ops[10];while (~scanf("%d%d", &n, &m)){init();for (i = 1; i <= n; ++i)scanf("%d", &arr[i]);for (i = 1; i < n; ++i){scanf("%d%d", &a, &b);add(a, b);add(b, a);}dfs1(1, 0, 1);dfs2(1, 1);build(1, 1, n);for (i = 1; i <= n; ++i)update(1, idx[i], idx[i], arr[i]);while (m--){scanf("%s", ops);if (ops[0] == 'Q'){scanf("%d%d", &a, &b);printf("%d\n", Find(a, b));}else{scanf("%d%d%d", &a, &b, &c);solve(a, b, c);}}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Blackops/p/7258037.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2243 染色（树链剖分好题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。