2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 7964 Solved: 2987
[Submit][Status][Discuss]
Description
給定一棵有n個節點的無根樹和m個操作,操作有2類:
1、将節點a到節點b路徑上所有點都染成顔色c;
2、詢問節點a到節點b路徑上的顔色段數量(連續相同顔色被認為是同一段),如“112221”由3段組成:“11”、“222”和“1”。
請你寫一個程式依次完成這m個操作。
Input
第一行包含2個整數n和m,分别表示節點數和操作數;
第二行包含n個正整數表示n個節點的初始顔色
下面 行每行包含兩個整數x和y,表示x和y之間有一條無向邊。
下面 行每行描述一個操作:
“C a b c”表示這是一個染色操作,把節點a到節點b路徑上所有點(包括a和b)都染成顔色c;
“Q a b”表示這是一個詢問操作,詢問節點a到節點b(包括a和b)路徑上的顔色段數量。
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
數N<=10^5,操作數M<=10^5,所有的顔色C為整數且在[0, 10^9]之間。
題解:樹鍊剖分+線段樹,注意每次查詢時查詢的是斷斷續續的區間,是以每次要繼續下上一次區間的資訊,如果兩次區間的始末位置顔色相同的話,合并之後的顔色數就要-1。
代碼:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = ;
int n,m;
int a[N],co[N];
struct node{
int pre,v;
}edge[N];
int num=,head[N];
void addedge(int from,int to){
num++;
edge[num].pre=head[from];
edge[num].v=to;
head[from]=num;
}
int fa[N],dep[N];
int siz[N],son[N];
void dfs1(int u,int f,int d){
siz[u]=,fa[u]=f,dep[u]=d;
for(int i=head[u];i;i=edge[i].pre){
int v=edge[i].v;
if(v==f) continue;
dfs1(v,u,d+);
siz[u]+=siz[v];
if(son[u]==-||siz[v]>siz[son[u]]) son[u]=v;
}
}
int indx=;
int in[N],out[N],top[N];
void dfs2(int u,int tp){
in[u]=out[u]=++indx;
co[indx]=a[u];
top[u]=tp;
if(son[u]==-) return ;
dfs2(son[u],tp);
for(int i=head[u];i;i=edge[i].pre){
int v=edge[i].v;
if(v==son[u]||v==fa[u]) continue;
dfs2(v,v);
}
out[u]=indx;
}
struct Node{
int ans;
int lx,rx;
int l,r;
int flag;
}t[N<<];
void update(int root){
if(t[root<<].rx==t[root<<|].lx)
t[root].ans=t[root<<].ans+t[root<<|].ans-;
else t[root].ans=t[root<<].ans+t[root<<|].ans;
t[root].lx=t[root<<].lx,t[root].rx=t[root<<|].rx;
}
void build(int root,int l,int r){
t[root].l=l,t[root].r=r,t[root].flag=;
if(l==r){
t[root].ans=;
t[root].lx=t[root].rx=co[l];
return ;
}
int mid=l+r>>;
build(root<<,l,mid);
build(root<<|,mid+,r);
update(root);
}
void pushdown(int root){
int flag=t[root].flag,l=t[root].l,r=t[root].r;
if(flag){
t[root<<].ans=t[root<<|].ans=;
t[root<<].lx=t[root<<].rx=flag;
t[root<<|].lx=t[root<<|].rx=flag;
t[root<<].flag=t[root<<|].flag=flag;
t[root].flag=;
}
}
void modify(int root,int pos,int val,int delta){
int l=t[root].l,r=t[root].r;
if(pos<=l&&val>=r){
t[root].ans=;
t[root].lx=t[root].rx=delta;
t[root].flag=delta;
return ;
}
int mid=l+r>>;
pushdown(root);
if(pos<=mid) modify(root<<,pos,val,delta);
if(val>mid) modify(root<<|,pos,val,delta);
update(root);
}
void modify(int u,int v,int delta){
int f1=top[u],f2=top[v];
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);
modify(,in[f1],in[u],delta);
u=fa[f1],f1=top[u];
}
if(dep[u]>dep[v]) swap(u,v);
modify(,in[u],in[v],delta);
}
int lc,rc;
int query(int root,int pos,int val,int L,int R){
int l=t[root].l,r=t[root].r;
if(l==L) lc=t[root].lx;
if(r==R) rc=t[root].rx;
if(pos==l&&val==r) return t[root].ans;
int mid=l+r>>;
pushdown(root);
if(val<=mid) return query(root<<,pos,val,L,R);
else if(pos>mid) return query(root<<|,pos,val,L,R);
else{
int a=query(root<<,pos,mid,L,R);
int b=query(root<<|,mid+,val,L,R);
if(t[root<<|].lx==t[root<<].rx) return a+b-;
else return a+b;
}
}
int query(int u,int v){
int f1=top[u],f2=top[v];
int sum=;
int co1=-,co2=-;
while(f1!=f2){
if(dep[f1]<dep[f2]) swap(f1,f2),swap(u,v),swap(co1,co2);
sum+=query(,in[f1],in[u],in[f1],in[u]);
if(rc==co1) sum--;
co1=lc;
u=fa[f1];
f1=top[u];
}
if(dep[u]<dep[v]) swap(u,v),swap(co1,co2);
sum+=query(,in[v],in[u],in[v],in[u]);
if(rc==co1) sum--;if(lc==co2) sum--;
return sum;
}
#define ms(x,y) memset(x,y,sizeof(x))
int main(){
ms(son,-);
scanf("%d%d",&n,&m);
for(register int i=;i<=n;i++) scanf("%d",&a[i]);
for(register int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
dfs1(,,);dfs2(,);
build(,,n);
while(m--){
char s[];
int u,v,delta;
scanf("%s",s);
if(s[]=='C'){
scanf("%d%d%d",&u,&v,&delta);
modify(u,v,delta);
}
else{
scanf("%d%d",&u,&v);
printf("%d\n",query(u,v));
}
}
return ;
}
7月60篇部落格達成。這個月真是勤勉。