首页 > 代码库 > zoj 1610 Count the Colors

zoj 1610 Count the Colors

2024-07-17 20:39:23   211人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=610

先用线段树维护区间颜色的覆盖，然后在把区间的颜色映射到数组，再从数组统计颜色。

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 100000  5 using namespace std;  6   7 int n;  8 int min1;  9 struct node1 10 { 11     int x1,x2,c; 12 }p[maxn]; 13 struct node 14 { 15     int l,r; 16     int cover; 17 }tree[maxn*4]; 18 int vis[maxn]; 19 int colo[maxn]; 20  21  22 void build(int i,int l,int r) 23 { 24     tree[i].l=l; tree[i].r=r; 25     tree[i].cover=-1; 26     if(l==r) return ; 27     int mid=(l+r)>>1; 28     build(i<<1,l,mid); 29     build(i<<1|1,mid+1,r); 30 } 31 void down(int i) 32 { 33     if(tree[i].l==tree[i].r) return ; 34     if(tree[i].cover!=-1) 35     { 36         tree[i<<1].cover=tree[i<<1|1].cover=tree[i].cover; 37         tree[i].cover=-1; 38     } 39 } 40 void update(int i,int l,int r,int col) 41 { 42     if(tree[i].l==l&&tree[i].r==r) 43     { 44         tree[i].cover=col; 45         return ; 46     } 47     down(i); 48     int mid=(tree[i].l+tree[i].r)>>1; 49     if(r<=mid) 50     { 51         update(i<<1,l,r,col); 52     } 53     else if(l>mid) 54     { 55         update(i<<1|1,l,r,col); 56     } 57     else 58     { 59         update(i<<1,l,mid,col); 60         update(i<<1|1,mid+1,r,col); 61     } 62 } 63  64 void search1(int i) 65 { 66     if(tree[i].cover!=-1) 67     { 68          for(int k=tree[i].l; k<=tree[i].r; k++) 69          { 70              vis[k]=tree[i].cover; 71          } 72          return ; 73     } 74     if(tree[i].l==tree[i].r) return; 75     search1(i<<1); 76     search1(i<<1|1); 77 } 78  79 int main() 80 { 81     while(scanf("%d",&n)!=EOF) 82     { 83         int max1=0,max2=-1; 84         min1=maxn; 85         for(int i=1; i<=n; i++) 86         { 87             scanf("%d%d%d",&p[i].x1,&p[i].x2,&p[i].c); 88             max1=max(max1,p[i].x2); 89             max2=max(max2,p[i].c); 90             min1=min(min1,p[i].c); 91         } 92         build(1,0,max1*2-1); 93         for(int i=0; i<=max1*2; i++) 94         { 95             vis[i]=-1; 96         } 97         for(int i=1; i<=n; i++) 98         { 99             update(1,p[i].x1*2,p[i].x2*2-1,p[i].c);100         }101         search1(1);102         memset(colo,0,sizeof(colo));103         for(int i=0; i<=max1*2; i++)104         {105             if(vis[i]!=-1)106             {107                 int mm=vis[i];108                 colo[mm]++;109                 while(vis[i]==mm&&i<=max1*2) i++;110             }111         }112         for(int i=min1; i<=max2; i++)113         {114             if(colo[i])115             {116                 printf("%d %d\n",i,colo[i]);117             }118         }119         printf("\n");120     }121     return 0;122 }
View Code

 


联系
我们