题目链接
输入输出格式
输入格式:
输出格式:
对于每个询问操作,输出一行答案。
输入输出样例
输入样例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
输出
4
2
4
2
1
2