ZOJ 1610

線段樹。線段覆蓋。成段更新。lazy標記處理。

下面是AC代碼：
[cpp]
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
const int maxn = 10000; 
struct node{ 
    int l,r; 
    int color; 
}T[maxn<<2]; 
void build (int id,int l,int r){ 
     T[id].l=l;T[id].r=r;T[id].color=-1; 
     if(l==r)  return ; 
     int m=(l+r)>>1; 
     build(id<<1,l,m);  build(id<<1|1,m+1,r); 
} 
int ans[maxn]; 
int res[maxn]; 
void update(int id,int l,int r,int color){ 
      if(T[id].l==l&&T[id].r==r){   T[id].color=color; return ; } 
      if(T[id].color!=-1){ 
            T[id<<1].color=T[id<<1|1].color=T[id].color; 
            T[id].color = -1; 
      } 
      int m=(T[id].l+T[id].r)>>1; 
      if(m>=r){ 
          update(id<<1,l,r,color); 
      } 
      else if(m<l){ 
          update((id<<1)|1,l,r,color); 
      } 
      else{ 
            update(id<<1,l,m,color); 
            update((id<<1)|1,m+1,r,color); 
      } 
} 
void query(int id,int l,int r){ 
    if(T[id].l==T[id].r){ 
         ans[l]=T[id].color; 
         return ; 
    } 
    int m=(l+r)>>1; 
    if(T[id].color!=-1){ 
        T[id<<1].color=T[id<<1|1].color=T[id].color; 
        T[id].color = -1; 
    } 
    query(id<<1,l,m); 
    query(id<<1|1,m+1,r); 
} 
int main(){ 
    int n,l,r,color; 
    while(scanf("%d",&n)!=EOF){ 
        memset(ans,0,sizeof(ans)); 
        memset(res,0,sizeof(res)); 
         build(1,1,8001); 
         for(int i=0;i<n;i++){ 
              scanf("%d%d%d",&l,&r,&color); 
              if(l>r) swap(l,r); 
              l++; 
            //  r++; 
              update(1,l,r,color); 
         } 
         query(1,1,8001); 
         ans[0]=-1; 
         for(int i=1;i<=8001;i++){ 
             if(ans[i]!=-1&&ans[i]!=ans[i-1]){ 
                res[ ans[i] ]++; 
             } 
         } 
 
         for(int i=0;i<=8001;i++){ 
             if(res[i]>0) 
               printf("%d %d\n",i,res[i]); 
         } 
         puts(""); 
    } 
    return 0; 
}