今天做到第二题，大部分的思路都理解了之后最后剩下一个问题
zzx：“然后扫描线+树状数组搞一下就好了”
看到这两个算法就产生了一种我肯定会的错觉...
然后后来发现并不会的时候很惭愧...
然后十分感谢YDC，在之前完全陌生的情况下 我去问这样一个问题
超级超级超级耐心地给我解答
我问着每一个他们看起来显然的具体处理方法
突然发现真的像张老师说的：“你普及升提高的这条路没有怎么走，中间那块知识是空着的啊”
今天才切实体会到...但是或许正是这样今天学到这样的一个东西更让我觉得开心吧
树状数组解决一维点线包含问题
事实上现在印象非常深刻，初二的时候做过一道苹果的题目，就是运用到树状数组
也是添加线段，然后查询当前点是否有苹果，当时可能还比较小
对这样解决方法并不是理解得十分透彻
1）添加线段（l,r）:put(l,1);put(r+1,-1);
2) 删除线段(l,r):put(l,-1);put(r+1,1);
3) 横坐标为x的点被覆盖的次数 = get(x);
其实很好理解...如果把树状数组理解成前缀和一样的东西，相当于x前有多少个左端点，多少个右端点
然后每一个左端点和一个右端点相互抵消
然后我们拓展到二维的情况
添加扫描线即可
对于一系列横坐标为x的点，我们需要在树状数组中的
是左边界<=x,右边界>x的矩形
1）我们只需要把还未添加进来的，左边界满足要求的添加进来
2）把已经添加进来的，右边界不满足要求的删掉即可
第一种情况显然是满足单调性的，然而第二种实际上也是
因为右边界都不满足要求了，即<x，那么左边界也一定<x，也就是这个矩形必然添加进来了
然后对于每一个矩形，其y坐标的区间进行树状数组的删添操作
然后对于这些点，get(y)就是被覆盖的次数
并没有找到这样的裸题，于是写了个暴力对拍
需要注意：
1）坐标往往需要离散化（当然为了偷懒这次就没写离散
2）一些点或者矩形有必要需要保存id，因为排序之后输出可能会影响答案（在某些题目中
3）如果题目中并没有明确告诉左上角和右下角的顺序，要记得交换
4）若边界上的点不算，则需要注意更多的细节
1 program sweep; 2 const maxn = 10010; 3 var i,n,m,j,k,head,tail:longint; 4 a,c:array[-1..maxn]of record x1,y1,x2,y2:longint;end; 5 b:array[-1..maxn]of record x,y,id:longint;end; 6 f,tr:array[-1..maxn]of longint; 7 8 procedure qsort1(L,R:longint); 9 var i,j,mid:longint; 10 begin 11 i:=L;j:=R;mid:=a[random(R-L+1)+L].x1; 12 repeat 13 while (i<R)and(a[i].x1<mid) do inc(i); 14 while (L<j)and(a[j].x1>mid) do dec(j); 15 if i<=j then 16 begin 17 a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; 18 inc(i);dec(j); 19 end; 20 until i>j; 21 if i<R then qsort1(i,R); 22 if L<j then qsort1(L,j); 23 end; 24 25 procedure qsort2(L,R:longint); 26 var i,j,mid:longint; 27 begin 28 i:=L;j:=R;mid:=b[random(R-L+1)+L].x; 29 repeat 30 while (i<R)and(b[i].x<mid) do inc(i); 31 while (L<j)and(b[j].x>mid) do dec(j); 32 if i<=j then 33 begin 34 b[0]:=b[i];b[i]:=b[j];b[j]:=b[0]; 35 inc(i);dec(j); 36 end; 37 until i>j; 38 if i<R then qsort2(i,R); 39 if L<j then qsort2(L,j); 40 end; 41 42 procedure qsort3(L,R:longint); 43 var i,j,mid:longint; 44 begin 45 i:=L;j:=R;mid:=c[random(R-L+1)+L].x2; 46 repeat 47 while (i<R)and(c[i].x2<mid) do inc(i); 48 while (L<j)and(c[j].x2>mid) do dec(j); 49 if i<=j then 50 begin 51 c[0]:=c[i];c[i]:=c[j];c[j]:=c[0]; 52 inc(i);dec(j); 53 end; 54 until i>j; 55 if i<R then qsort3(i,R); 56 if L<j then qsort3(L,j); 57 end; 58 59 procedure put(x,y:longint); 60 begin 61 while x<=maxn do 62 begin 63 inc(tr[x],y); 64 x:=x+x and (-x); 65 end; 66 end; 67 68 function get(x:longint):longint; 69 begin 70 get:=0; 71 while x<>0 do 72 begin 73 inc(get,tr[x]); 74 x:=x-x and (-x); 75 end; 76 end; 77 78 begin 79 assign(input,‘sweep.in‘);reset(input); 80 assign(output,‘sweep.out‘);rewrite(output); 81 readln(n,m); 82 for i:=1 to n do readln(a[i].x1,a[i].y1,a[i].x2,a[i].y2); 83 //读入矩形左上角和右下角（为了偷懒没有交换23333 84 for i:=1 to m do begin readln(b[i].x,b[i].y);b[i].id:=i;end; 85 //读入点坐标 86 qsort1(1,n); //按照做边界排序矩形 87 qsort2(1,m); 88 c:=a;qsort3(1,n); //按照右边界排序矩形 89 head:=1;tail:=1;i:=1; 90 while i<=m do 91 begin 92 while (tail<=n)and(a[tail].x1<=b[i].x) do 93 begin 94 put(a[tail].y1,1); 95 put(a[tail].y2+1,-1); 96 inc(tail); 97 end; 98 //把左边界包含点的矩形添加进来 99 while (head<=n)and(c[head].x2<b[i].x) do 100 begin 101 put(c[head].y1,-1); 102 put(c[head].y2+1,1); 103 inc(head); 104 end; 105 //把右边界已经跳出点的矩形删去 106 j:=i+1; 107 while (j<=m)and(b[j].x=b[i].x) do inc(j); 108 for k:=i to j-1 do f[b[k].id]:=get(b[k].y); 109 i:=j; 110 end; 111 for i:=1 to m do writeln(f[i]); 112 end.
#在做题之前多想一些细节总是好的
21/.Aprl
原文：http://www.cnblogs.com/mjy0724/p/4445430.html