题目描述

在一个1000米长的桌子上放着很多盒子，桌子的后方有一堵墙，如下图所示。假设人站得足够远，问：从桌子前方可以看到多少个盒子？

思路

用线段树记录一个值c=0为未完全覆盖，c>=1时每个数表示一种颜色，开一个f数组标记每种颜色是否出现过，就可以了
O(logn)

#include <stdio.h>
struct tree
{
    int l,r,c;
}t[1000005];
int fl[1000000];
int insert(int f,int x,int y,int i)
{
    if (t[f].c!=i)
    {
        int m=(t[f].l+t[f].r)/2;
        if (t[f].l==x&&t[f].r==y) t[f].c=i;
        else
        {
            if (t[f].c!=0)
            {
                t[f*2].c=t[f*2+1].c=t[f].c;
                t[f].c=0;
            }
            if (y<=m) insert(f*2,x,y,i);
            else if (x>=m) insert(f*2+1,x,y,i);
            else 
            {
                insert(f*2,x,m,i);
                insert(f*2+1,m,y,i);
            }
        }
    }
}
int count(int f)
{
    if (t[f].c!=0)
        fl[t[f].c]=1;
    else if (t[f].r-t[f].l==0)
        return 0;
    else return count(f*2)+count(f*2+1);
}
int create(int f)
{
    if (t[f].l!=t[f].r-1)
    {
        int m=(t[f].l+t[f].r)/2;
        t[f*2].l=t[f].l;
        t[f*2].r=m;
        t[f*2+1].l=m;
        t[f*2+1].r=t[f].r;
        create(f*2);
        create(f*2+1);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    t[1].l=1; t[1].r=n;
    create(1);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert(1,x,y,i);
    }
    count(1);
    int ans=0;
    for (int i=1;i<=1000000;i++)
        if (fl[i]==1) ans++;
    printf("%d\n",ans);
}