题目描述

桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

思路

用线段树记录下每一个区间，暴力求解就可以了
O(logn)

#include <stdio.h>
struct tree
{
    int l,r,c;
}t[1000];
int insert(int f,int x,int y)
{
    if (t[f].c==0)
    {
        int m=(t[f].l+t[f].r)/2;
        if (t[f].l==x&&t[f].r==y) t[f].c=1;
        else if (y<=m) insert(f*2,x,y);
        else if (x>=m) insert(f*2+1,x,y);
        else 
        {
            insert(f*2,x,m);
            insert(f*2+1,m,y);
        }
    }
}
int count(int f)
{
    if (t[f].c==1)
        return t[f].r-t[f].l;
    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);
    }
    printf("%d\n",count(1));
}