题目描述
桌子上零散地放着若干个盒子,桌子的后方是一堵墙。如右图所示。现在从桌子的前射来一束平行光, 把盒子的影子投射到了墙上。问影子的总宽度是多少?
思路
用线段树记录下每一个区间,暴力求解就可以了
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)); }
Comments NOTHING