首页 > 代码库 > 【bzoj2243】[SDOI2011]染色

【bzoj2243】[SDOI2011]染色

2024-08-27 08:59:49   220人阅读

题目描述

给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

输入

第一行包含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）路径上的颜色段数量。

输出

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

样例输入

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

样例输出

3
1
2

提示

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

题解

 

裸的树链剖分+线段树。
区间修改非常恶心，很多细节。
多写写应该就能好了吧。。。
  1 #include <stdio.h>
  2 #include <algorithm>
  3 using namespace std;
  4 #define lson l , mid , x << 1
  5 #define rson mid + 1 , r , x << 1 | 1
  6 #define N 100005
  7 int fa[N] , deep[N] , si[N] , val[N] , bl[N] , pos[N] , tot;
  8 int head[N] , to[N << 1] , next[N << 1] , cnt;
  9 int sum[N << 3] , lc[N << 3] , rc[N << 3] , mark[N << 3] , n;
 10 char str[10];
 11 void add(int x , int y)
 12 {
 13     to[++cnt] = y;
 14     next[cnt] = head[x];
 15     head[x] = cnt;
 16 }
 17 void dfs1(int x)
 18 {
 19     int i , y;
 20     si[x] = 1;
 21     for(i = head[x] ; i ; i = next[i])
 22     {
 23         y = to[i];
 24         if(y != fa[x])
 25         {
 26             fa[y] = x;
 27             deep[y] = deep[x] + 1;
 28             dfs1(y);
 29             si[x] += si[y];
 30         }
 31     }
 32 }
 33 void dfs2(int x , int c)
 34 {
 35     int k = 0 , i , y;
 36     bl[x] = c;
 37     pos[x] = ++tot;
 38     for(i = head[x] ; i ; i = next[i])
 39     {
 40         y = to[i];
 41         if(fa[x] != y && si[y] > si[k])
 42             k = y;
 43     }
 44     if(k != 0)
 45     {
 46         dfs2(k , c);
 47         for(i = head[x] ; i ; i = next[i])
 48         {
 49             y = to[i];
 50             if(fa[x] != y && y != k)
 51                 dfs2(y , y);
 52         }
 53     }
 54 }
 55 void pushup(int x)
 56 {
 57     lc[x] = lc[x << 1];
 58     rc[x] = rc[x << 1 | 1];
 59     sum[x] = sum[x << 1] + sum[x << 1 | 1];
 60     if(rc[x << 1] == lc[x << 1 | 1])
 61         sum[x] -- ;
 62 }
 63 void pushdown(int x)
 64 {
 65     int tmp = mark[x];
 66     mark[x] = 0;
 67     if(tmp)
 68     {
 69         sum[x << 1] = sum[x << 1 | 1] = 1;
 70         lc[x << 1] = rc[x << 1] = lc[x << 1 | 1] = rc[x << 1 | 1] = tmp;
 71         mark[x << 1] = mark[x << 1 | 1] = tmp;
 72     }
 73 }
 74 void update(int b , int e , int v , int l , int r , int x)
 75 {
 76     pushdown(x);
 77     if(b <= l && r <= e)
 78     {
 79         sum[x] = 1;
 80         lc[x] = rc[x] = v;
 81         mark[x] = v;
 82         return;
 83     }
 84     int mid = (l + r) >> 1;
 85     if(b <= mid)
 86         update(b , e , v , lson);
 87     if(e > mid)
 88         update(b , e , v , rson);
 89     pushup(x);
 90 }
 91 void solveupdate(int x , int y , int v)
 92 {
 93     while(bl[x] != bl[y])
 94     {
 95         if(deep[bl[x]] < deep[bl[y]])
 96         {
 97             swap(x , y);
 98         }
 99         update(pos[bl[x]] , pos[x] , v , 1 , n , 1);
100         x = fa[bl[x]];
101     }
102     if(deep[x] > deep[y])
103         swap(x , y);
104     update(pos[x] , pos[y] , v , 1 , n , 1);
105 }
106 int query(int b , int e , int l , int r , int x)
107 {
108     pushdown(x);
109     if(b <= l && r <= e)
110     {
111         return sum[x];
112     }
113     int mid = (l + r) >> 1 , ans = 0;
114     if(b <= mid)
115         ans += query(b , e , lson);
116     if(e > mid)
117         ans += query(b , e , rson);
118     if(b <= mid && e > mid && rc[x << 1] == lc[x << 1 | 1])
119         ans -- ;
120     return ans;
121 }
122 int getcl(int p , int l , int r , int x)
123 {
124     pushdown(x);
125     if(l == r)
126         return lc[x];
127     int mid = (l + r) >> 1;
128     if(p <= mid)
129         return getcl(p , lson);
130     else
131         return getcl(p , rson);
132 }
133 int solvequery(int x , int y)
134 {
135     int ans = 0;
136     while(bl[x] != bl[y])
137     {
138         if(deep[bl[x]] < deep[bl[y]])
139             swap(x , y);
140         ans += query(pos[bl[x]] , pos[x] , 1 , n , 1);
141         if(getcl(pos[bl[x]] , 1 , n , 1) == getcl(pos[fa[bl[x]]] , 1 , n , 1))
142             ans -- ;
143         x = fa[bl[x]];
144     }
145     if(deep[x] > deep[y])
146         swap(x , y);
147     ans += query(pos[x] , pos[y] , 1 , n , 1);
148     return ans;
149 }
150 int main()
151 {
152     int i , x , y , z , m;
153     scanf("%d%d" , &n , &m);
154     for(i = 1 ; i <= n ; i ++ )
155         scanf("%d" , &val[i]);
156     for(i = 1 ; i < n ; i ++ )
157     {
158         scanf("%d%d" , &x , &y);
159         add(x , y);
160         add(y , x);
161     }
162     dfs1(1);
163     dfs2(1 , 1);
164     for(i = 1 ; i <= n ; i ++ )
165         update(pos[i] , pos[i] , val[i] , 1 , n , 1);
166     while(m -- )
167     {
168         scanf("%s" , str);
169         switch(str[0])
170         {
171             case ‘C‘: scanf("%d%d%d" , &x , &y , &z); solveupdate(x , y , z); break;
172             default: scanf("%d%d" , &x , &y); printf("%d\n" , solvequery(x , y));
173         }
174     }
175     return 0;
176 }

【bzoj2243】[SDOI2011]染色


联系
我们