本文共 2173 字，大约阅读时间需要 7 分钟。

链接：

题目大意：

在一条长度为8000的线段上染色，每次把区间[a,b]染成c颜色。显然，后面染上去的颜色会覆盖掉之前的颜色。

求染完之后，每个颜色在线段上有多少个间断的区间。

分析与总结：

这题是成段更新lazy标记的题，并不算难，但是因为一些原因一直让我过不去。。。

1. 昨天做了这题，但是一直连样例都出不来 = =～！早上起来，突然醒悟发现了问题所在，题目每次给的染色段是把[a,b]染成c，之前一直以为就是把a～b的所有点都染成c， 其实不是这样的，要染色的不是点，而是区间，例如要染[0,1]，并不是把0，1两点染色，而是把[0,1]这一个单位区间进行染色。 假设有一个样例：

1  2  1

3  4  1

那么这个样例应该输出1  2. 只需要在纸上画一下就可以发现，区间【2，3】是没有被染色的，所以有两个间断的区间颜色是1。

解决这个问题的办法是，建立线段树build(1,1,8000)，代表区间1～8000， 然后更新时是update(1,1,8000, a+1,b,c);

2. 由于没有仔细看题目，看错了一个地方，于是一直RE（在zoj上叫做Segmentation Fault）：

The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

代码：

#include
   
    #include
    
     #include
     
      #define mem(str,x) memset(str,(x),sizeof(str))#define FOR(i,s,t) for(int i=(s); i<(t); ++i)#define FF(i,n) for(int i=0; i<(n); ++i)#define mid ((left+right)>>1)#define len (right-left+1)#define lson rt<<1, left, m#define rson rt<<1|1, m+1, right#define STOP puts("Stop Here~");using namespace std;const int MAXN = 8005;int n,col[MAXN<<2],vis[MAXN<<2],ans[MAXN<<2];inline void push_down(int rt){    if(col[rt] != -1){        col[rt<<1] = col[rt<<1|1] = col[rt];        col[rt] = -1;    }}void update(int rt,int left,int right,int l,int r,int data){    if(l<=left && right<=r){        col[rt] = data;        return;    }    if(col[rt] == data) return;    if(col[rt]!=-1)push_down(rt);    int m = mid;    if(l <= m)update(lson,l,r,data);    if(r > m)update(rson,l,r,data);}void query(int rt,int left,int right){    if(col[rt]>=0){        for(int i=left; i<=right; ++i)            vis[i] = col[rt];        return;    }    if(left!=right && col[rt] == -1){        int m = mid;        query(lson);        query(rson);    }}int main(){    int a,b,c;    while(~scanf("%d",&n)){        memset(col,-1,sizeof(col));        for(int i=0; i
      
       =b)continue;            update(1,1,8000,a+1,b,c);        }        mem(vis,-1);         query(1,1,8000);        int i = 1;        mem(ans,0);        while(i
      
     
    
   

          原创  ， By   D_Double  (转载请标明)