P2486 [SDOI2011]染色

题目链接

P2486 [SDOI2011]染色

输入输出格式

输入格式：

输出格式：

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

输入输出样例

输入样例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 来查询单点的颜色，其他学过树剖的应该不会太陌生

区间修改
与普通的树剖题修改无大异，注意线段树中的颜色数量更新即区间端点继承即可

细节很多，要注意，不仅在树上查询要注意端点的问题，在线段树也要注意，我调了很久都是因为在线段树的查询中没有注意端点问题！！！！

代码

#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
连接写的超级赞，本篇题解搬照与次，做日后方便查看使用:点我点我

输入

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

输出