--- title: P2486 [SDOI2011]染色 date: 2019-12-01 19:37:09 tags: - 树链剖分 categories: - ACM ---  <!--more--> ## 题目链接 [P2486 [SDOI2011]染色](https://www.luogu.com.cn/problem/P2486) ## 输入输出格式 ### 输入格式：  ### 输出格式： 对于每个询问操作，输出一行答案。 ## 输入输出样例 ### 输入样例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 ``` ## 说明   ## 题解 这是这题的难点，弄懂了以后可以对线段树有个蛮大的提升 我们先把问题简化一下，假设这不是一棵树，只是一条连（已经树剖过了），给定每个元素的颜色，问有几段颜色（就是这题中颜色数量的定义），我们怎么做呢？ 首先我们可以知道，为了保障时间复杂度，这题肯定是用线段树求解的，最先想到的是叶子节点的颜色个数为1，因为此时不存在有颜色会重复，按线段树的做法，现在要回溯求更大区间的颜色个数了，我们怎样求解呢？ 其实分情况讨论一下就可以知道了：见下 第一种情况： 左区间：1231（颜色个数为4） 右区间：222（个数为1） 合并后：1231222（颜色个数为4+1=5） 这是第一种情况：没有重复 我们再来看第二种： 左区间：1231（颜色个数为4）右区间：121（个数为3） 合并后：1231121（颜色个数为4+3-1） 这就是第二种情况了，左区间的最后一个颜色和右区间的第一个颜色重合，也就重复了，所以总数减一 综上所述：我们用线段树维护左右颜色，区间颜色总数，就可以解决链情况下的此问题了 值得注意的是：**不要忘记大区间要继承小区间的左右端点颜色** **树上查询颜色个数** 我们的操作时基于树形的，所以树剖过后，我们树剖的查询函数要略作修改。  如上图：树剖就是把两点之间剖成了若干条链，我们还是要解决不同的链之间颜色重复问题。上图已经很明朗了：解决`top[a]` 与 `fa[top[a]]` 颜色重复问题即可： 我写了个函数 `Qc` 来查询单点的颜色，其他学过树剖的应该不会太陌生 **区间修改** 与普通的树剖题修改无大异，注意线段树中的颜色数量更新即区间端点继承即可 细节很多，要注意，不仅在树上查询要注意端点的问题，在线段树也要注意，我调了很久都是因为在线段树的查询中没有注意端点问题！！！！ ## 代码 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 5; const int INF = 0x3f3f3f3f; struct Node{ int l,r,lazy,lc,rc,num; int mid(){ return (l + r) >> 1; } }tree[MAXN << 2]; int n,m,a[MAXN]; int fa[MAXN],siz[MAXN],son[MAXN],dep[MAXN]; int top[MAXN],dfn[MAXN],tim,w[MAXN]; vector<int> E[MAXN]; void AddEdge(int u,int v){ E[u].push_back(v); E[v].push_back(u); } void PushUp(int rt){ int rrt = rt << 1|1; int ans = tree[rt << 1].num + tree[rrt].num; tree[rt].lc = tree[rt << 1].lc,tree[rt].rc = tree[rrt].rc; if(tree[rt << 1].rc == tree[rrt].lc) ans--; tree[rt].num = ans; } void PushDown(int rt){ int rrt = rt << 1|1; tree[rt << 1].lazy = tree[rrt].lazy = tree[rt].lazy; tree[rt << 1].num = tree[rrt].num = 1; tree[rt << 1].lc = tree[rrt].rc = tree[rt].lazy; tree[rrt].lc = tree[rt << 1].rc = tree[rt].lazy; tree[rt].lazy = -1; } void Build(int l,int r,int rt){ tree[rt].l = l,tree[rt].r = r,tree[rt].lazy = -1; if(l == r){ tree[rt].rc = tree[rt].lc = w[l]; tree[rt].num = 1; return ; } int mid = tree[rt].mid(); Build(l,mid,rt << 1); Build(mid+1,r,rt << 1|1); PushUp(rt); } void Update(int l,int r,int rt,int val){ if(tree[rt].l == l && tree[rt].r == r){ tree[rt].num = 1; tree[rt].lazy = val; tree[rt].lc = tree[rt].rc = val; return ; } if(tree[rt].lazy != -1) PushDown(rt); int mid = tree[rt].mid(); if(mid < l){ Update(l,r,rt << 1|1,val); } else if(mid >= r) { Update(l,r,rt << 1,val); } else { Update(l,mid,rt << 1,val); Update(mid+1,r,rt << 1|1,val); } PushUp(rt); } int Query(int l,int r,int rt){ if(tree[rt].l == l && tree[rt].r == r){ return tree[rt].num; } int ret = 0,mid = tree[rt].mid(); if(tree[rt].lazy != -1) PushDown(rt); if(mid < l){ ret += Query(l,r,rt << 1|1); } else if(mid >= r) { ret += Query(l,r,rt << 1); } else { ret += Query(l,mid,rt << 1) + Query(mid+1,r,rt << 1|1); if(tree[rt << 1].rc == tree[rt << 1|1].lc) ret--; } return ret; } void dfs1(int u,int f){ dep[u] = dep[f] + 1; fa[u] = f; siz[u] = 1; int sz = E[u].size(),maxsiz = -1; for(int i = 0;i < sz;i++){ int v = E[u][i]; if(v == f) continue; dfs1(v,u); siz[u] += siz[v]; if(siz[v] > maxsiz){ maxsiz = siz[v]; son[u] = v; } } } void dfs2(int u,int t){ top[u] = t; dfn[u] = ++tim; w[tim] = a[u]; if(!son[u]) return ; dfs2(son[u],t); int sz = E[u].size(); for(int i = 0;i < sz;i++){ int v = E[u][i]; if(v == fa[u] || v == son[u]) continue; dfs2(v,v); } } int Qcolor(int pos,int rt){ if(tree[rt].l == pos && tree[rt].r == pos) return tree[rt].lc; int mid = tree[rt].mid(); if(tree[rt].lazy != -1) PushDown(rt); if(pos <= mid) return Qcolor(pos,rt << 1); else return Qcolor(pos,rt << 1|1); } int Qchain(int x,int y){ int ret = 0,Scolo,Fcolo; while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x,y); ret += Query(dfn[top[x]],dfn[x],1); Scolo = Qcolor(dfn[top[x]],1); Fcolo = Qcolor(dfn[fa[top[x]]],1); if(Scolo == Fcolo) ret--; x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); ret += Query(dfn[x],dfn[y],1); return ret; } void mchain(int x,int y,int z){ while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x,y); Update(dfn[top[x]],dfn[x],1,z); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); Update(dfn[x],dfn[y],1,z); } int main() { ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i < n;i++){ int u,v; cin >> u >> v; AddEdge(u,v); } dfs1(1,0); dfs2(1,1); Build(1,n,1); while(m--){ char op; int x,y,z; cin >> op; if(op == 'Q'){ cin >> x >> y; printf("%d\n",Qchain(x,y)); } else { cin >> x >> y >> z; mchain(x,y,z); } } return 0; } ``` 附上几组写的时候用到的数据(洛谷论坛看到的)，还有参照的一位大佬的Blog 连接写的超级赞，本篇题解搬照与次，做日后方便查看使用:[点我点我](https://www.cnblogs.com/Tony-Double-Sky/p/9283262.html) 输入 ``` 10 4 26 22 46 21 10 46 43 9 11 33 2 1 3 2 4 3 5 2 6 5 7 3 8 7 9 5 10 5 C 10 1 28 C 4 5 17 Q 7 10 Q 10 7 ``` 输出 ``` 3 3 ``` 输入 ``` 6 12 0 0 11 4 2 6 5 4 3 5 3 1 1 2 6 5 Q 2 6 C 3 1 3 Q 4 5 Q 2 6 Q 2 3 C 3 3 5 Q 2 1 C 3 4 3 C 2 4 2 Q 1 3 Q 1 6 C 4 3 6 ``` 输出 ``` 4 2 4 2 1 2 ```