程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj 1610 Count the Colors

zoj 1610 Count the Colors

編輯：C++入門知識

zoj 1610 Count the Colors

題意

給0-8000區間染色，最後有多少個顏色區間，並且出現了多少次

思路

線段樹成段更新
注意點：
就是
1-2 1
3-4 1
並不是連接在一起的是兩段
所以我們可以在更新的時候使 l=l+1
這樣就是兩段了
代碼還是很簡單的

代碼

/* **********************************************
Auther: 請叫我acm渣渣
Created Time: 2015-7-29 20:01:25
File Name   : color.cpp
*********************************************** */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lson L,m,rt<<1
#define rson m+1,R,rt<<1|1
#define ll long long
#define N 11111

int color[N<<2];
int vis[N<<2];
int ans[N<<2];

void pushdown(int rt){
    if(color[rt]!=-1){
      color[rt<<1]=color[rt<<1|1]=color[rt];
      color[rt]=-1;
    }
}

void update(int L,int R,int rt,int l,int r, int c){
    if(l<=L&&r>=R){
        color[rt]=c;
        return;
    }
    pushdown(rt);
    int m = (L+R)>>1;
    if(l<=m) update(lson,l,r,c);
    if(r>m)  update(rson,l,r,c);
}

void query(int L,int R,int rt){
    if(color[rt]!=-1){
        for(int i = L;i<=R;i++){
            vis[i]=color[rt];
        }
        return ;
    }
    if(L==R) return;
    int m = (L+R)>>1;
    query(lson);
    query(rson);
}

int main(){
    int n;
    int o = 8000;
    while(scanf(%d,&n)==1){
        memset(vis,-1,sizeof(vis));
        memset(color,-1,sizeof(color));
        memset(ans,0,sizeof(ans));
        int mx = -1;
        for(int i=1;i<=n;i++){
            int a,b,c;
            scanf(%d%d%d,&a,&b,&c);
            if(a>=b) continue;
            mx = max(c,mx);
            update(1,o,1,a+1,b,c);
        }

        query(1,o,1);

        for(int i=1;i<=o;i++){
            if(vis[i]==-1) continue;
            int h = i;
            int c = vis[i];
            while(vis[h]==c) h++;
            ans[c]++;
            i=h-1;
        }

        for(int i=0;i<=mx;i++){
            if(ans[i]){
            printf(%d %d
,i,ans[i]);
            }
        }
        puts();
    }
}