zoj 1610 Count the Colors 线段树区间更新

题目链接:

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

题意:

题解:

线段树区间更新
注意更新子节点，如果遇到的父节点已经被颜色覆盖掉的话，父节点的颜色需要往下传递（因为父节点已经不会是原来那种颜色了）。

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 8e3+10;
 17 
 18 struct node{
 19     int l,r,col,lazy;
 20 }t[maxn<<2];
 21 
 22 void build(int rt,int l,int r){
 23     t[rt].l=l,t[rt].r=r,t[rt].col=-1,t[rt].lazy=-1;
 24     if(l == r) return ;
 25     int mid = (l+r)/2;
 26     build(rt<<1,l,mid);
 27     build(rt<<1|1,mid+1,r);
 28 }
 29 
 30 void pushdown(int rt){
 31     if(t[rt].lazy != -1){
 32         t[rt<<1].lazy=t[rt<<1|1].lazy = 1;
 33         t[rt<<1].col = t[rt].col;
 34         t[rt<<1|1].col = t[rt].col;
 35         t[rt].lazy = t[rt].col = -1;
 36     }
 37 }
 38 
 39 void update(int rt,int l,int r,int c){
 40     int L=t[rt].l,R=t[rt].r;
 41     if(l<=L && R<=r) {
 42         t[rt].col = c;
 43         t[rt].lazy = 1;
 44         return ;
 45     }
 46     if(t[rt].col == c) return ;
 47     pushdown(rt);
 48     int mid = (L+R)/2;
 49     if(l<=mid) update(rt<<1,l,r,c);
 50     if(r>mid) update(rt<<1|1,l,r,c);
 51 }
 52 
 53 
 54 int vis[maxn<<2],ans[maxn<<2];
 55 
 56 void query(int rt){
 57     int l = t[rt].l,r=t[rt].r;
 58     if(t[rt].lazy == 1){
 59         int c = t[rt].col;
 60         for(int i=l; i<=r; ++i)
 61             vis[i] = c;
 62         return ;
 63     }
 64     if(l == r) return ;
 65     query(rt<<1);  
 66     query(rt<<1|1);  
 67 }
 68 
 69 int main(){
 70     int n;
 71     while(cin>>n){
 72         build(1,1,maxn);
 73         for(int i=0; i<n; i++){
 74             int l,r,c; cin>>l>>r>>c;
 75             update(1,l+1,r,c); 
 76 // 题目每次给的染色段是把[a,b]染成c，之前一直以为就是把a～b的所有点都染成c， 其实不是这样的，
 77 // 要染色的不是点，而是区间，例如要染[0,1]，并不是把0，1两点染色，而是把[0,1]这一个单位
 78 // 区间进行染色。 假设有一个样例：
 79 // 1  2  1
 80 // 3  4  1
 81 // 那么这个样例应该输出 1  2  只需要在纸上画一下就可以发现，区间【2，3】是没有被染色的，
 82 // 所以有两个间断的区间颜色是1。
 83 // 解决这个问题的办法是，建立线段树build(1,1,8000)，代表区间1～8000， 
 84 // 然后更新时是update(1,1,8000, a+1,b,c);
 85         }
 86 
 87         memset(vis,-1,sizeof(vis)); 
 88         query(1);
 89         int i = 1;  
 90 
 91         MS(ans);  
 92         while(i<maxn){  
 93             int color=vis[i], j=i+1;  
 94             if(color==-1){++i; continue;}  
 95             while(vis[j]!=-1 && vis[j]==color && j<maxn) ++j;  // 统计的是点。。
 96             ++ans[color];  
 97             i=j;  
 98         }  
 99         for(int i=0; i<maxn; ++i)if(ans[i])  
100             printf("%d %d
",i,ans[i]);  
101         puts("");   
102     }
103 
104     return 0;
105 }

zoj 1610 Count the Colors 线段树 区间更新

题目链接:

题意:

题解:

代码:

zoj 1610 Count the Colors 线段树区间更新