[bzoj 2243]: [SDOI2011]染色 [树链剖分][线段树]

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

HINT

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

My Solution

一道可爱的树链剖分题啊

注意区间合并和树剖中的calc即可

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 inline int read(){

     char ch;

     int re=;

     bool flag=;

     while((ch=getchar())!='-'&&(ch<''||ch>''));

     ch=='-'?flag=:re=ch-'';

     while((ch=getchar())>=''&&ch<='')  re=re*+ch-'';

     return flag?-re:re;

 }

 inline char rea(){

     char ch;

     while((ch=getchar())!='Q'&&ch!='C');

     return ch;

 }

 struct edge{

     int to,next;

     edge(int to=,int next=):

         to(to),next(next){}

 };

 struct segment{

     int l,r,lc,rc,sum,tag;

 };

 const int maxn=1e5+;

 edge edges[maxn<<];

 segment tre[maxn<<];

 int n,m,cnt=,root;

 //si1,si2表示query操作中取到的最高和最低颜色

 int si1,si2,LL,RR;

 int head[maxn],data[maxn];

 int siz[maxn],fat[maxn],son[maxn],dep[maxn],id[maxn],id_[maxn],top[maxn];

 inline void add_edge(int from,int to){

     edges[++cnt]=edge(to,head[from]);  head[from]=cnt;

     edges[++cnt]=edge(from,head[to]);  head[to]=cnt;

 }

 void init(){

     n=read();  m=read();

     for(int i=;i<=n;i++)  data[i]=read();

     int from,to;  cnt=;

     for(int i=;i<n;i++){

         from=read();  to=read();

         add_edge(from,to);

     }

 }

 void dfs_1(int x,int fa){

     siz[x]=;

     dep[x]=dep[fa]+;

     fat[x]=fa;

     for(int ee=head[x];ee;ee=edges[ee].next)

         if(edges[ee].to!=fa){

             dfs_1(edges[ee].to,x);

             siz[x]+=siz[edges[ee].to];

             if(!son[x]||siz[edges[ee].to]>siz[son[x]])  son[x]=edges[ee].to;

         }

 }

 void dfs_2(int x,int first){

     top[x]=first;

     id[x]=++cnt;

     id_[cnt]=x;

     if(!son[x])  return;

     dfs_2(son[x],first);

     for(int ee=head[x];ee;ee=edges[ee].next)

         if(edges[ee].to!=fat[x]&&edges[ee].to!=son[x])  dfs_2(edges[ee].to,edges[ee].to);

 }

 void push_up(int x){

     int lson=x<<,rson=lson|;

     tre[x].lc=tre[lson].lc;

     tre[x].rc=tre[rson].rc;

     tre[x].sum=tre[lson].sum+tre[rson].sum-(tre[lson].rc==tre[rson].lc?:);

 }

 void build(int x,int l,int r){

     tre[x].l=l;  tre[x].r=r;

     if(l==r){

         tre[x].lc=tre[x].rc=data[id_[l]];

         tre[x].sum=;

         return;

     }

     int mid=(l+r)>>;

     build(x<<,l,mid);  build(x<<|,mid+,r);

     push_up(x);

 }

 void push_down(int x){

     int lson=x<<,rson=lson|;

     int &c=tre[x].tag;

     tre[lson].tag=tre[rson].tag=tre[lson].lc=

     tre[lson].rc=tre[rson].lc=tre[rson].rc=c;

     tre[lson].sum=;  tre[rson].sum=;

     c=;

 }

 void make(){

     root=;  dfs_1(root,);

     cnt=;  dfs_2(root,root);

     build(,,n);

 }

 void update(int x,int L,int R,int c){

     if(L<=tre[x].l&&tre[x].r<=R){

         tre[x].lc=tre[x].rc=tre[x].tag=c;

         tre[x].sum=;

         return;

     }

     if(tre[x].tag)  push_down(x);

     int mid=(tre[x].l+tre[x].r)>>;

     if(R<=mid)  update(x<<,L,R,c);

     else  if(L>mid)  update(x<<|,L,R,c);

     else{

         update(x<<,L,mid,c);

         update(x<<|,mid+,R,c);

     }

     push_up(x);

 }

 int query_sum(int x,int L,int R){

     if(tre[x].l==LL)  si1=tre[x].lc;

     if(tre[x].r==RR)  si2=tre[x].rc;

     if(L<=tre[x].l&&tre[x].r<=R)  return tre[x].sum;

     if(tre[x].tag)  push_down(x);

     int mid=(tre[x].l+tre[x].r)>>;

     if(R<=mid)  return query_sum(x<<,L,R);

     if(L>mid)  return query_sum(x<<|,L,R);

     return query_sum(x<<,L,mid)+query_sum(x<<|,mid+,R)-(tre[x<<].rc==tre[x<<|].lc?:);

 }

 void calc(int ss,int tt,int c){

     int f1=top[ss],f2=top[tt];

     while(f1!=f2){

         if(dep[f1]<dep[f2]){  swap(f1,f2);  swap(ss,tt);  }

         update(,id[f1],id[ss],c);

         ss=fat[f1];  f1=top[ss];

     }

     if(dep[ss]<dep[tt])  swap(ss,tt);

     update(,id[tt],id[ss],c);

 }

 int calc(int ss,int tt){

     int f1=top[ss],f2=top[tt],ans=;

     int sid1=,sid2=;

     while(f1!=f2){

         if(dep[f1]<dep[f2]){  swap(f1,f2);  swap(ss,tt);  swap(sid1,sid2);  }

         LL=id[f1];  RR=id[ss];

         ans+=query_sum(,id[f1],id[ss]);

         if(si2==sid1)  ans--;

         sid1=si1;  ss=fat[f1];  f1=top[ss];

     }

     if(dep[ss]<dep[tt])  {  swap(ss,tt);  swap(sid1,sid2);  }

     LL=id[tt];  RR=id[ss];

     ans+=query_sum(,id[tt],id[ss]);

     if(sid1==si2)  ans--;

     if(sid2==si1)  ans--;

     return ans;

 }

 void solve(){

     char opt;

     int ss,tt,c;

     for(int i=;i<m;i++){

         opt=rea();

         switch(opt){

             case 'C':{

                 ss=read();  tt=read();  c=read();

                 calc(ss,tt,c);

                 break;

             }

             case 'Q':{

                 ss=read();  tt=read();

                 printf("%d\n",calc(ss,tt));

                 break;

             }

         }

     }

 }

 int main(){

     //freopen("data.in","r",stdin);

     init();

     make();

     solve();

     return ;

 }

それまでは閉じこもって

あなたも卵の中なのね

秒客网