P2486 [SDOI2011]染色

ACM 阅读量

题目链接

P2486 [SDOI2011]染色

输入输出格式

输入格式：

输出格式：

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

输入输出样例

输入样例1：

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

输出样例1：

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

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

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

代码

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#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
连接写的超级赞，本篇题解搬照与次，做日后方便查看使用:点我点我

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

输出

1
2
3
3

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

输出

1
2
3
4
5
6
4
2
4
2
1
2

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :