首页 > 代码库 > [bzoj 2243]: [SDOI2011]染色 [树链剖分][线段树]
[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
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
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
My Solution
一道可爱的树链剖分题啊
注意区间合并和树剖中的calc即可
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 inline int read(){ 7 char ch; 8 int re=0; 9 bool flag=0; 10 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘)); 11 ch==‘-‘?flag=1:re=ch-‘0‘; 12 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘; 13 return flag?-re:re; 14 } 15 16 inline char rea(){ 17 char ch; 18 while((ch=getchar())!=‘Q‘&&ch!=‘C‘); 19 return ch; 20 } 21 22 struct edge{ 23 int to,next; 24 edge(int to=0,int next=0): 25 to(to),next(next){} 26 }; 27 28 struct segment{ 29 int l,r,lc,rc,sum,tag; 30 }; 31 32 const int maxn=1e5+1; 33 34 edge edges[maxn<<1]; 35 segment tre[maxn<<2]; 36 int n,m,cnt=1,root; 37 //si1,si2表示query操作中取到的最高和最低颜色 38 int si1,si2,LL,RR; 39 int head[maxn],data[maxn]; 40 int siz[maxn],fat[maxn],son[maxn],dep[maxn],id[maxn],id_[maxn],top[maxn]; 41 42 inline void add_edge(int from,int to){ 43 edges[++cnt]=edge(to,head[from]); head[from]=cnt; 44 edges[++cnt]=edge(from,head[to]); head[to]=cnt; 45 } 46 47 void init(){ 48 n=read(); m=read(); 49 for(int i=1;i<=n;i++) data[i]=read(); 50 int from,to; cnt=0; 51 for(int i=1;i<n;i++){ 52 from=read(); to=read(); 53 add_edge(from,to); 54 } 55 } 56 57 void dfs_1(int x,int fa){ 58 siz[x]=1; 59 dep[x]=dep[fa]+1; 60 fat[x]=fa; 61 for(int ee=head[x];ee;ee=edges[ee].next) 62 if(edges[ee].to!=fa){ 63 dfs_1(edges[ee].to,x); 64 siz[x]+=siz[edges[ee].to]; 65 if(!son[x]||siz[edges[ee].to]>siz[son[x]]) son[x]=edges[ee].to; 66 } 67 } 68 69 void dfs_2(int x,int first){ 70 top[x]=first; 71 id[x]=++cnt; 72 id_[cnt]=x; 73 if(!son[x]) return; 74 dfs_2(son[x],first); 75 for(int ee=head[x];ee;ee=edges[ee].next) 76 if(edges[ee].to!=fat[x]&&edges[ee].to!=son[x]) dfs_2(edges[ee].to,edges[ee].to); 77 } 78 79 void push_up(int x){ 80 int lson=x<<1,rson=lson|1; 81 tre[x].lc=tre[lson].lc; 82 tre[x].rc=tre[rson].rc; 83 tre[x].sum=tre[lson].sum+tre[rson].sum-(tre[lson].rc==tre[rson].lc?1:0); 84 } 85 86 void build(int x,int l,int r){ 87 tre[x].l=l; tre[x].r=r; 88 if(l==r){ 89 tre[x].lc=tre[x].rc=data[id_[l]]; 90 tre[x].sum=1; 91 return; 92 } 93 int mid=(l+r)>>1; 94 build(x<<1,l,mid); build(x<<1|1,mid+1,r); 95 push_up(x); 96 } 97 98 void push_down(int x){ 99 int lson=x<<1,rson=lson|1;100 int &c=tre[x].tag;101 tre[lson].tag=tre[rson].tag=tre[lson].lc=102 tre[lson].rc=tre[rson].lc=tre[rson].rc=c;103 tre[lson].sum=1; tre[rson].sum=1;104 c=0;105 }106 107 void make(){108 root=1; dfs_1(root,0);109 cnt=0; dfs_2(root,root);110 build(1,1,n);111 }112 113 void update(int x,int L,int R,int c){114 if(L<=tre[x].l&&tre[x].r<=R){115 tre[x].lc=tre[x].rc=tre[x].tag=c;116 tre[x].sum=1;117 return;118 }119 120 if(tre[x].tag) push_down(x);121 122 int mid=(tre[x].l+tre[x].r)>>1;123 if(R<=mid) update(x<<1,L,R,c);124 else if(L>mid) update(x<<1|1,L,R,c);125 else{126 update(x<<1,L,mid,c);127 update(x<<1|1,mid+1,R,c);128 }129 push_up(x);130 }131 132 int query_sum(int x,int L,int R){133 if(tre[x].l==LL) si1=tre[x].lc;134 if(tre[x].r==RR) si2=tre[x].rc;135 if(L<=tre[x].l&&tre[x].r<=R) return tre[x].sum;136 137 if(tre[x].tag) push_down(x);138 139 int mid=(tre[x].l+tre[x].r)>>1;140 if(R<=mid) return query_sum(x<<1,L,R);141 if(L>mid) return query_sum(x<<1|1,L,R);142 return query_sum(x<<1,L,mid)+query_sum(x<<1|1,mid+1,R)-(tre[x<<1].rc==tre[x<<1|1].lc?1:0);143 }144 145 void calc(int ss,int tt,int c){146 int f1=top[ss],f2=top[tt];147 while(f1!=f2){148 if(dep[f1]<dep[f2]){ swap(f1,f2); swap(ss,tt); }149 update(1,id[f1],id[ss],c);150 ss=fat[f1]; f1=top[ss];151 }152 if(dep[ss]<dep[tt]) swap(ss,tt);153 update(1,id[tt],id[ss],c);154 }155 156 int calc(int ss,int tt){157 int f1=top[ss],f2=top[tt],ans=0;158 int sid1=0,sid2=0;159 while(f1!=f2){160 if(dep[f1]<dep[f2]){ swap(f1,f2); swap(ss,tt); swap(sid1,sid2); }161 LL=id[f1]; RR=id[ss];162 ans+=query_sum(1,id[f1],id[ss]);163 if(si2==sid1) ans--;164 sid1=si1; ss=fat[f1]; f1=top[ss];165 }166 if(dep[ss]<dep[tt]) { swap(ss,tt); swap(sid1,sid2); }167 LL=id[tt]; RR=id[ss];168 ans+=query_sum(1,id[tt],id[ss]);169 if(sid1==si2) ans--;170 if(sid2==si1) ans--;171 return ans;172 }173 174 void solve(){175 char opt;176 int ss,tt,c;177 for(int i=0;i<m;i++){178 opt=rea();179 switch(opt){180 case ‘C‘:{181 ss=read(); tt=read(); c=read();182 calc(ss,tt,c);183 break;184 }185 case ‘Q‘:{186 ss=read(); tt=read();187 printf("%d\n",calc(ss,tt));188 break;189 }190 }191 }192 }193 194 int main(){195 //freopen("data.in","r",stdin);196 init();197 make();198 solve();199 return 0;200 }
それまでは 閉じこもって
あなたも卵の中なのね
[bzoj 2243]: [SDOI2011]染色 [树链剖分][线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。