ZOJ 1610 Count the Colors （线段树 成段更新）

题目链接

题意：成段染色，初始为0，每次改变一个区间的颜色，求最后每种颜色分别有多少段。颜色按照从

小到大输出。

分析：改变了代码的风格，因为看了学长的博客。直接用数组，可以只是记录节点的编号，因为节点编号

确定了，则l，r也就确定了。

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #define LL __int64

 #define lson l, mid, 2*rt

 #define rson mid+1, r, 2*rt+1

 const int maxn = +;

 using namespace std;

 int val[*maxn], num[maxn];

 void pushdown(int rt)  //如果没有更新，向下更新

 {

     if(val[rt]!=-)

     {

         val[*rt] = val[rt];

         val[*rt+] = val[rt];

         val[rt] = -;

     }

 }

 void update(int ll, int rr, int c, int l, int r, int rt) //ll，rr代表要找的区间，不用减小了，一直都是这个

 {

     if(ll<=l && rr>=r) //如果当前节点的范围在 改变的节点的范围内就 改变

     {

         val[rt] = c;

         return;

     }

     pushdown(rt);

     int mid = (l+r)/;

     if(ll<=mid) update(ll, rr, c, lson);  //看这个左半区间内是否还有点

     if(rr>mid) update(ll, rr, c, rson);

 }

 int query(int p, int l, int r, int rt)

 {

     if(l>p) return ;

     if(r<p) return ;

     if(p==l&&p==r) return val[rt];

     if(p>=l && p<=r && val[rt]!=-) return val[rt];

     int mid = (l+r)/;

     return query(p, lson)+query(p, rson);

 }

 int main()

 {

     int i, n, l, r, c, x, pre;

     while(~scanf("%d", &n))

     {

         memset(val, -, sizeof(val)); //相当于建树

         memset(num, , sizeof(num));

         while(n--)

         {

             scanf("%d%d%d", &l, &r, &c);

             if(r- >= l)

             update(l, r-, c, , , );

         }

         pre = -;

         for(i = ; i <= ; i++) //查询的是区间00，11.。。

         {

            x = query(i, , , );

            if(x!=pre) //如果不连续 就加上

            {

                pre = x;

               if(x>=) num[x]++;

            }

         }

         for(i = ; i <= ; i++)

         {

             if(num[i])

             printf("%d %d\n", i, num[i]);

         }

         printf("\n");

     }

     return ;

 }