题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610
题目大意：在一条线上绘制一些彩色片段，一些先前绘制的片段可能被后续的一些片段覆盖。您的任务是计算最后可以看到的不同颜色的片段。

每个数据集的第一行恰好包含一个整数n，1 <= n <= 8000，等于彩色段的数量。以下n行中的每一行由正好由单个空格分隔的3个非负整数组成：x1 x2 c
x1和x2表示段的左端点和右端点，c表示段的颜色。

所有数字都在[0,8000]范围内，它们都是整数。输入可能包含多个数据集，处理到文件末尾。

输出：输出的每一行应包含一个颜色索引，可以从顶部看到，按照这种颜色的分段计数，它们应根据颜色索引打印。如果看不到某种颜色，则不应打印。
在每个数据集后打印一个空行。

之前遇到过数组含义的问题，这里如果对x, y区间染c色，UP(1, x, y, c)更新。
那么此时节点的含义是区间的端点。

所以到最后，知道端点的含义并不知道区间的颜色。就会认为最后只能看见两种颜色。

如果我们把节点i的含义改[i-1, i]区间的颜色，那么就可以了，UP(1, x+1, y, c)更新。

然后改完还是WA了。有个奇怪的错误，就是建树的时候，我建了8001个节点WA了。改成8000个就AC。不知道这是为什么。

思考：注意对数组和节点代表的含义。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

#define MAX_NODE 800005
#define MAX_ 200005

struct NODE
{
    int l, r;

}node[MAX_NODE];
int f[MAX_];     //记录节点i的node结构体数组下标f[i]
int add[MAX_NODE];

void BT(int i, int l ,int r)   //建树
{
    node[i].l=l;
    node[i].r=r;
    if(l==r)                   //根节点
    {
        f[l]=i;
        return;
    }
    BT((i<<1), l, (l+r)/2);    //建左子树
    BT((i<<1)+1, (l+r)/2+1, r);//建右子树

}

void upadd(int i)
{
    if(add[i])
    {
        add[i<<1]=add[i];          //把左右子的add标记进行更新
        add[(i<<1)+1]=add[i];

        add[i]=0;                   //清零父节点的add标记
    }
}

void UP(int i, int l, int r, int c)//更新
{
    if(node[i].l==l&&node[i].r==r)//找到更新区间
    {
        add[i]=c;                //更新add标记

        return;
    }

    if(node[i].l==node[i].r)      //叶子节点
    {
        add[i]=c;
        return;
    }

    upadd(i);                     //把此本节点的add往下移动

    int mid=(node[i].l+node[i].r)/2;//继续寻找区间
    if(r<=mid)                    //全在左区间
    {
        UP(i<<1, l, r, c);
    }
    else if(l>mid)                //全在右区间
    {
        UP((i<<1)+1, l, r, c);
    }
    else
    {
        UP(i<<1, l, mid, c);
        UP((i<<1)+1, mid+1, r, c);
    }

}

void FD(int i, int l, int r)   //查找
{
    if(l==r)
    {
        return;
    }
    upadd(i);
    FD(i<<1, l, (l+r)/2);
    FD((i<<1)+1, (l+r)/2+1, r);

}
//建树 BT(1, 1 ,n);节点1-n
//查询 FD(1, a, b);[a, b]的信息
//更新 UP(1, a, b, c);//把区间的add+=a

int c[8001];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c, 0, sizeof(c));
        memset(add, 0, sizeof(add));
        BT(1, 1, 8000);
        for(int i=1;i<=n;i++)
        {
            int a, b, c;
            scanf("%d%d%d",&a,&b,&c);
            UP(1, a+1, b, c+1);
        }
        FD(1, 1, 8000);
        int ans=0;
        for(int i=1;i<=8000;i++)
        {
            if(add[f[i]]!=add[f[i-1]]&&add[f[i]]!=0)
            {
                c[add[f[i]]-1]++;
            }
        }
        for(int i=0;i<=8000;i++)
        {
            if(c[i]!=0)
            {
                printf("%d %d\n",i, c[i]);
            }
        }
        printf("\n");

    }

    return 0;
}