ZOJ 1610 Count the Colors

题意是有一个无色的长为8000的线段，将会有 n 次操作 x1 ,x2,c 将以x1为左端点以x2为右端点的区域染成颜色c(以[0,8000]区间里的数字指示颜色)，之前的颜色可能会被之后的染色覆盖，试问最后每种颜色各有几段。（长度为1的段可视作"小段"，连续的同色"小段"拼成一段）

这题可以将小段化作点，染色可以看做区间修改，只用最后一次查询，不妨使用永久化标记，给每次染色增加一个额外属性的时间戳，最后可以DFS得到每一个"小段"的颜色（搜索过程中记录染色情况，以时间戳大的染色为答案），再O(8000)扫一遍即可。

 1 #pragma GCC optimize("O3", "unroll-loops")
 2 #pragma target("avx2")
 3 
 4 #include <bits/stdc++.h>
 5 using namespace std;
 6 #define Lson(x) ((x)<<1)
 7 #define Rson(x) ((x)<<1|1)
 8 const int maxn = 8000+1;
 9 const pair<int ,int > KONG = make_pair(0,0);
10 pair< int , int > lazy[(maxn<<2)+10];//first 是时间戳 ， second is color
11 int ans[maxn+10]; // 最后染色结果
12 int printout[maxn + 10];// 输出答案
13 void build(int s,int t,int p){
14     if(s==t){
15         lazy[p] = KONG;
16         return ;
17     }
18     lazy[p] = KONG;
19     int mid = (s + t )>>1;
20     build(s,mid,Lson(p));
21     build(mid+1,t,Rson(p));
22 }
23 
24 void update(int L,int R,pair<int,int> C,int s,int t,int p){
25     if(L == s && t == R){
26         lazy[p] = max(lazy[p],C);
27         return ;
28     }
29     int mid = (s + t) >> 1;
30     if(R<=mid) update(L,R,C,s,mid,Lson(p));
31     else if(L>mid) update(L,R,C,mid+1,t,Rson(p));
32     else update(L,mid,C,s,mid,Lson(p)),update(mid+1,R,C,mid+1,t,Rson(p));
33 }
34 
35 void DFS(int s,int t,int p,pair<int ,int> ran){
36     ran = max(ran,lazy[p]);
37     if(s==t){
38         ans[s] = ran.second;
39         return;
40     }
41     int mid = (s + t )>> 1;
42     DFS(s,mid,Lson(p),ran);
43     DFS(mid + 1,t,Rson(p),ran);
44 }
45 
46 int main(){
47     int N;
48     while(~scanf("%d",&N)){
49         build(1,maxn,1);
50         for(int i=1;i<=N;++i){
51             int L,R,C;
52             scanf("%d%d%d",&L,&R,&C);
53             L ++ , R , C++;// 化段为点　0作为无色
54             update(L,R,make_pair(i,C),1,maxn,1);
55         }
56         DFS(1,maxn,1,KONG);
57 
58         memset(printout,0,sizeof(printout));
59         int ind = 1;
60 //        puts("ans :");for(int i=1;i<=10;++i) printf("%d%c",ans[i]-1,i==10?'
':' ');
61         while(ind <= maxn){
62             if(ans[ind] && ind != maxn){
63                 for(int j=ind + 1;j<=maxn;++j){
64                     if(ans[j]!=ans[ind]){
65                         printout[ans[ind]-1] ++;
66                         ind = j;
67                         break;
68                     }
69                 }
70             }
71             else if(ans[ind]){
72                 printout[ans[ind]-1] ++;
73             }
74             else ind ++;
75         }
76         for(int i=0;i<=maxn;++i)
77             if(printout[i]) printf("%d %d
",i,printout[i]);
78         puts("");
79     }
80     return 0;
81 }

View Code

有多组数据，每次记得初始化标记为时间戳为0且无色状态。