箱子_线段树

lzusa 发布于 2019-05-14 2 次阅读


题目描述

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


思路

用线段树记录下每一个区间,暴力求解就可以了
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));
}