自己做的是从下往上扫描的，一直wa，不知道坑在哪里。。但是作为模板。我还是找了份不错的ac代码
/* 被覆盖不低于k次的点 每个点对应了一个单位面积，本题把点转面积即是被覆盖不低于k次的面积 可以当做求k次面积覆盖模板的题目！ */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<map> using namespace std; #define maxn 60005 #define lson l,m,rt<<1 #define rson m,r,rt<<1|1 #define ll long long int n,k; struct Seg{ int l,r,h,c; Seg(){} Seg(int l,int r,int h,int c):l(l),r(r),h(h),c(c){} bool operator<(const Seg& a)const { return h<a.h; } }segs[maxn]; int tot,totx,x[maxn];//线段树建立在x轴上 int len[maxn<<2][12],flag[maxn<<2]; map<int,int>mp; inline void pushup(int rt,int l,int r){ if(flag[rt]>=k){ for(int i=1;i<=k;i++) len[rt][i]=0; len[rt][k]=x[r]-x[l]; } else if(flag[rt]>0){ int cur=flag[rt];//当前区间覆盖次数 for(int i=1;i<=k;i++) len[rt][i]=0;//先把当前区间所有覆盖情况置零 len[rt][cur]=x[r]-x[l]; if(l+1==r) return; for(int i=1;i<=k;i++){ if(i+cur>=k) len[rt][k]+=len[rt<<1][i]+len[rt<<1|1][i]; else len[rt][i+cur]+=len[rt<<1][i]+len[rt<<1|1][i]; } for(int i=cur+1;i<=k;i++) len[rt][cur]-=len[rt][i]; } else { for(int i=1;i<=k;i++) len[rt][i]=0; if(l+1==r) return; for(int i=1;i<=k;i++) len[rt][i]=len[rt<<1][i]+len[rt<<1|1][i]; } } void update(int L,int R,int c,int l,int r,int rt){ if(L<=l && R>=r){ flag[rt]+=c;; pushup(rt,l,r); return; } int m=l+r>>1; if(L<m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); pushup(rt,l,r); } void init(){ tot=totx=0; mp.clear(); memset(len,0,sizeof len); memset(flag,0,sizeof flag); } int main(){ int T,a,b,c,d; cin >> T; for(int tt=1;tt<=T;tt++){ init(); scanf("%d%d",&n,&k); for(int i=0;i<n;i++){ scanf("%d%d%d%d",&a,&b,&c,&d); c++;d++; segs[tot++]=Seg(a,c,b,1); segs[tot++]=Seg(a,c,d,-1); x[totx++]=a;x[totx++]=c; } sort(x,x+totx); sort(segs,segs+tot); totx=unique(x,x+totx)-x; for(int i=0;i<totx;i++) mp[x[i]]=i; ll res=0; for(int i=0;i<tot;i++){ if(i!=0) res+=(segs[i].h-segs[i-1].h)*len[1][k]; // cout<<segs[i].h-segs[i-1].h<< " "<<len[1][k]<<' '; update(mp[segs[i].l],mp[segs[i].r],segs[i].c,0,totx-1,1); } printf("Case %d: %lld ",tt,res); } return 0; }