zoj 1610 Count the Colors

点击打开链接zoj 1610

思路：线段树成段更新
分析：
1 题目给定n个区间的更新，然后要我们输出在这写所有的区间内能够见到的颜色的次数，只有连续的才算一次
2 简单的线段树的成段更新，做n的update，最后在查询一下然后输出

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 8010;
struct Node{
   int left;
   int right;
   int mark;
};
Node node[4*MAXN];
int ans[MAXN];
int n;

//向下更新
void push_down(int pos){
    if(node[pos].mark != -1){
       node[pos<<1].mark = node[pos].mark;
       node[(pos<<1)+1].mark = node[pos].mark;
       node[pos].mark = -1;
    }
}

//建立线段树
void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = -1;//延时标记初始化为-1
    if(left == right)
       return;
    int mid = (left+right)>>1;
    buildTree(left , mid , pos<<1);
    buildTree(mid+1 , right , (pos<<1)+1);
}

//更新
void update(int left , int right , int value , int pos){
    if(left <= node[pos].left && right >= node[pos].right){
       node[pos].mark = value;
       return;
    }
    push_down(pos);
    int mid = (node[pos].left+node[pos].right)>>1;
    if(right <= mid)
       update(left , right , value , pos<<1);
    else if(left > mid)
       update(left , right , value , (pos<<1)+1);
    else{
       update(left , mid , value , pos<<1);
       update(mid+1 , right , value , (pos<<1)+1);
    }
}

//查询
int query(int index , int pos){
    if(node[pos].left ==  node[pos].right)
      return node[pos].mark;
    push_down(pos);
    int mid = (node[pos].left + node[pos].right)>>1;
    if(index <= mid)
        return query(index , pos<<1);
    else
        return query(index , (pos<<1)+1);
}

int main(){
    int x , y , c;
    int Min_left , Max_right;
    int Min_Color , Max_Color;
    while(scanf("%d" , &n) != EOF){
        memset(ans , 0 , sizeof(ans));
        Min_left = MAXN , Min_Color = MAXN;
        Max_right = 0 , Max_Color = 0;
        buildTree(1 , MAXN , 1);
        for(int i = 0 ; i < n ; i++){
           scanf("%d%d%d" , &x , &y , &c);
           update(x+1 , y , c , 1);//这个地方我是把最左端+1
           Min_left = min(x , Min_left);
           Max_right = max(y , Max_right);
           Min_Color = min(c , Min_Color);
           Max_Color = max(c , Max_Color);
        }
        //查询的技巧
        int pre = query(Min_left+1 , 1);
        ans[pre]++;
        for(int i = Min_left+2 ; i <= Max_right ; i++){
           int tmp = query(i , 1);
           if(tmp != pre){
             ans[tmp]++;
             pre = tmp;
           }
        }
        //输出
        for(int i = Min_Color ; i <= Max_Color ; i++){
           if(ans[i])
             printf("%d %d\n" , i , ans[i]);
        }
        printf("\n");
    }
    return 0;
}