题意：给出n个矩形，求矩形中被覆盖K次以上的面积的和。
解法：整体与求矩形面积并差不多，不过在更新pushup改变len的时候，要有一层循环，来更新tree[rt].len[i]，其中tree[rt].len[i]表示覆盖次数大于等于i的线段长度，以便求面积，最后只要每次都用tree[1].len[K]来算面积即可。
代码：
#include <iostream> #include <cmath> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define ll long long using namespace std; #define N 30007 struct node { int cov; ll len[12]; }tree[8*N]; struct Line { ll y1,y2,x; int cov; }line[2*N]; ll yy[2*N]; int K; int cmp(Line ka,Line kb) { return ka.x < kb.x; } void addLine(ll x1,ll x2,ll y1,ll y2,int &m) { line[m].x = x1,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = 1,yy[m++] = y1; line[m].x = x2,line[m].y1 = y1,line[m].y2 = y2,line[m].cov = -1,yy[m++] = y2; } int bsearch(int l,int r,ll x) { while(l <= r) { int mid = (l+r)/2; if(yy[mid] == x) return mid; if(yy[mid] < x) l = mid+1; else r = mid-1; } return l; } void build(int l,int r,int rt) { tree[rt].cov = 0; memset(tree[rt].len,0,sizeof(tree[rt].len)); if(l+1 == r) return; int mid = (l+r)/2; build(l,mid,2*rt); build(mid,r,2*rt+1); } void pushup(int l,int r,int rt) { int cov = tree[rt].cov; for(int i=0;i<=K;i++) { if(cov >= i) tree[rt].len[i] = yy[r]-yy[l]; else if(l+1 == r) tree[rt].len[i] = 0; else tree[rt].len[i] = tree[2*rt].len[i-cov] + tree[2*rt+1].len[i-cov]; } } void update(int l,int r,int aa,int bb,int cov,int rt) { if(aa <= l && bb >= r) { tree[rt].cov += cov; pushup(l,r,rt); return; } if(l+1 == r) return; int mid = (l+r)/2; if(aa <= mid) update(l,mid,aa,bb,cov,2*rt); if(bb > mid) update(mid,r,aa,bb,cov,2*rt+1); pushup(l,r,rt); } int main() { int t,cs = 1,n,m,i,j; ll x1,x2,y1,y2; yy[0] = 0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&K); m = 1; for(i=0;i<n;i++) { scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); x2++,y2++; addLine(x1,x2,y1,y2,m); } if(K > n) { printf("Case %d: %d ",cs++,0); continue; } m--; sort(yy+1,yy+m+1); int cnt = 2; for(i=2;i<=m;i++) { if(yy[i] != yy[i-1]) yy[cnt++] = yy[i]; } cnt--; build(1,cnt,1); sort(line+1,line+m+1,cmp); ll ans = 0; for(i=1;i<m;i++) { int L = bsearch(1,cnt,line[i].y1); int R = bsearch(1,cnt,line[i].y2); update(1,cnt,L,R,line[i].cov,1); ans += tree[1].len[K]*(line[i+1].x-line[i].x); } printf("Case %d: %lld ",cs++,ans); } return 0; }
线段树求矩形面积交也可用类似方法，令K = 2即可