题意:
求矩形覆盖K次以上的面积
分析:
k很小，可以开K颗线段树,用sum[rt][i]来保存覆盖i次的区间和,K次以上全算K次
// File Name: 11983.cpp // Author: Zlbing // Created Time: 2013/7/21 16:06:54 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 0x3f3f3f3f #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int MAXN=6e4+100; struct seg{ int x1,x2,y; int flag; bool operator <(const seg& rsh)const{ return y<rsh.y; } }G[MAXN]; int hash[MAXN]; int col[MAXN<<2]; int sum[MAXN<<2][15]; int n,m; void build(int l,int r,int rt) { col[rt]=0; sum[rt][0]=hash[r+1]-hash[l]; for(int i=1;i<=m;i++)sum[rt][i]=0; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson); } void pushup(int rt,int l,int r) { if(col[rt]>=m) { memset(sum[rt],0,sizeof(sum[rt])); sum[rt][m]=hash[r+1]-hash[l]; } else if(l==r) { memset(sum[rt],0,sizeof(sum[rt])); sum[rt][col[rt]]=hash[r+1]-hash[l]; } else{ for(int i=0;i<col[rt];i++)sum[rt][i]=0; for(int i=col[rt];i<m;i++) { sum[rt][i]=sum[rt<<1][i-col[rt]]+sum[rt<<1|1][i-col[rt]]; } sum[rt][m]=0; for(int i=m-col[rt];i<=m;i++) { sum[rt][m]+=sum[rt<<1][i]+sum[rt<<1|1][i]; } } } void update(int L,int R,int flag,int l,int r,int rt) { if(L<=l&&R>=r) { col[rt]+=flag; pushup(rt,l,r); return; } int m=(l+r)>>1; if(L<=m)update(L,R,flag,lson); if(R>m)update(L,R,flag,rson); pushup(rt,l,r); } int main() { int T; scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d",&n,&m); int a,b,c,d; int xlen=0; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); c++,d++; G[xlen]=(seg){a,c,b,1}; //G[xlen].x1=a,G[xlen].x2=c,G[xlen].y=b,G[xlen].flag=1; hash[xlen]=a; xlen++; G[xlen]=(seg){a,c,d,-1}; //G[xlen].x1=a,G[xlen].x2=c,G[xlen].y=d,G[xlen].flag=-1; hash[xlen]=c; xlen++; } sort(G,G+xlen); sort(hash,hash+xlen); int len=unique(hash,hash+xlen)-hash; LL ans=0; build(0,xlen-1,1); for(int i=0;i<xlen-1;i++) { int x1=lower_bound(hash,hash+len,G[i].x1)-hash; int x2=lower_bound(hash,hash+len,G[i].x2)-hash-1; update(x1,x2,G[i].flag,0,xlen-1,1); //printf("sum[1][m]=%I64d h=%d ",sum[1][m],G[i+1].y-G[i].y); ans+=(LL)sum[1][m]*(LL)(G[i+1].y-G[i].y); } printf("Case %d: %lld ",cas++,ans); } return 0; }