扫描线，线段树求矩形并的面积
给了 n 的矩形，求被矩形覆盖 k 次及以上的点的个数。
首先将 x2, y2 分别加 1 便转化为求面积的问题。
将 x 坐标离散化以后，用线段树维护区间 [l, r] 中，被覆盖 k 次的长度。
由于 k 最大为10，那么将大于等于 k 次都看成 k 次，于是线段树中每个结点只需要开一个长度为 11 的数组。
对于一个矩形 (x1, y1, x2, y2), 我们将它分成两条线段 (x1, x2, y1, 1) 和 (x1, x2, y2, -1)。
把 2n 条线按照 y 坐标从小到大排序，用扫描线依次扫每一条线段。
遇到 1 则表示区间 [x1, x2] 覆盖次数加 1； 遇到 -1 则表示区间 [x1, x2] 覆盖次数减 1。
由于每次查询都是整个区间的覆盖次数，即只看线段树根结点的信息，因此结点的懒标记不用下放，只需要通过左右儿子以及当前结点的懒标记来更新当前结点的信息。
详见代码 Update 函数，cover 表示整个区间被覆盖的次数，cnt[i] 表示被覆盖 i 次的长度。
每扫到一条线段，需要先计算这条线段与上一条线段 y 坐标的差值，乘上整个区间被覆盖 k 次的长度，得到被覆盖 k 次的面积，所有的面积和即使所有答案。
然后再用这条线段更新线段树。
需要注意的是，由于离散化了 x 坐标，所以离散后的每个点是左闭右开的区间，计算区间 [l, r] 的长度时，应该是 x[r+1] - x[l]。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <queue> 5 #include <algorithm> 6 7 using namespace std; 8 9 #define MAXN 60010 10 #define INF 0x3f3f3f3f 11 #define MAX(a,b) (a>b?a:b) 12 #define MIN(a,b) (a<b?a:b) 13 #define ABS(m) (m<0?-m:m) 14 #define mo 1000000007 15 typedef long long LL; 16 17 int n,k,x[MAXN]; 18 19 struct RECTANGULAR 20 { 21 int x1,x2,y1,y2; 22 }rect[MAXN]; 23 24 struct LINE 25 { 26 int x1,x2,y,t; 27 bool operator<(const LINE &z) const{ 28 return y<z.y; 29 } 30 }line[MAXN]; 31 32 struct SegmentTree 33 { 34 int cover,cnt[11]; 35 }tree[MAXN*4]; 36 37 void Update(int i,int l,int r) 38 { 39 memset(tree[i].cnt,0,sizeof(tree[i].cnt)); 40 if(tree[i].cover>=k) tree[i].cnt[k]=x[r+1]-x[l]; 41 else if(l==r) tree[i].cnt[tree[i].cover]=x[r+1]-x[l]; 42 else{ 43 for(int j=0;j<=k;++j) 44 tree[i].cnt[MIN(k,(j+tree[i].cover))]+=tree[i*2].cnt[j]+tree[i*2+1].cnt[j]; 45 } 46 } 47 48 void Build(int i,int l,int r) 49 { 50 tree[i].cover=0; 51 memset(tree[i].cnt,0,sizeof(tree[i].cnt)); 52 tree[i].cnt[0]=x[r+1]-x[l]; 53 if(l==r) return; 54 int mid=(l+r)>>1; 55 Build(i*2,l,mid); 56 Build(i*2+1,mid+1,r); 57 } 58 59 void Modify(int i,int l,int r,int s,int t,int val) 60 { 61 if(s<=l && r<=t){ 62 tree[i].cover+=val; 63 Update(i,l,r); 64 return; 65 } 66 int mid=(l+r)>>1; 67 if(l<=t&&mid>=s) Modify(i*2,l,mid,s,t,val); 68 if(mid<t&&r>=s) Modify(i*2+1,mid+1,r,s,t,val); 69 Update(i,l,r); 70 } 71 72 void Init() 73 { 74 int i,l,r,mid; 75 scanf("%d%d",&n,&k); 76 for(i=1;i<=n;++i){ 77 scanf("%d%d%d%d",&rect[i].x1,&rect[i].y1,&rect[i].x2,&rect[i].y2); 78 ++rect[i].x2; ++rect[i].y2; 79 x[i]=rect[i].x1; 80 x[i+n]=rect[i].x2; 81 } 82 sort(x+1,x+1+n*2); 83 x[0]=unique(x+1,x+1+n*2)-x-1; 84 for(i=1;i<=n;++i){ 85 line[i].y=rect[i].y1; line[i+n].y=rect[i].y2; 86 line[i].t=1; line[i+n].t=-1; 87 for(l=1,r=x[0];l<r;mid=(l+r)>>1,x[mid]<rect[i].x1?l=mid+1:r=mid); 88 line[i].x1=line[i+n].x1=r; 89 for(l=1,r=x[0];l<r;mid=(l+r)>>1,x[mid]<rect[i].x2?l=mid+1:r=mid); 90 line[i].x2=line[i+n].x2=r; 91 } 92 sort(line+1,line+1+n*2); 93 } 94 95 LL Work() 96 { 97 int i; 98 LL ans=0; 99 for(i=1;i<=n*2;++i){ 100 if(i>1 && line[i].y!=line[i-1].y) 101 ans+=1LL*tree[1].cnt[k]*(line[i].y-line[i-1].y); 102 Modify(1,1,x[0]-1,line[i].x1,line[i].x2-1,line[i].t); 103 } 104 return ans; 105 } 106 107 int main() 108 { 109 int i,t; 110 for(scanf("%d",&t),i=1;i<=t;++i){ 111 Init(); 112 Build(1,1,x[0]-1); 113 printf("Case %d: %I64d\n",i,Work()); 114 } 115 return 0; 116 }
UVA - 11983 - Weird Advertisement
UVA - 11983 - Weird Advertisement
原文：http://www.cnblogs.com/orenjisora/p/5002567.html
