對于這類面積覆寫的題，大緻就兩點要注意的
1.同一把矩形放在笛卡爾坐标系上做
2.pushup函數要注意下細節:及在統計子區間和之前要先判斷是否有子區間
用sum數組來儲存區間被覆寫的情況，如果遇到多次覆寫問題，那就開多個sum數組分别儲存被覆寫n次的情況
用cnt數組儲存區間被完全覆寫的次數，如果是不同類型的矩形需要分别統計或者有特殊要求，那就開多個cnt數組分别儲存
pushup如果cnt[rt]超過了k次，滿足要求，那麼就直接把sum[k]指派為目前區間長度，然後其他sum數組歸零，結束傳回
否則如果cnt[rt]不為0，先把所有該區間的sum置零，然後把覆寫了該區間cnt[rt]次對應的sum指派為目前區間長度如果rt沒有子區間就傳回，有子區間 i 就從1循環到k，如果cnt[rt]+i>=k,那麼對應的sum[k]就是兩個子區間的被覆寫i次的長度和，否則sum[i+cnt[rt]]就是兩個子區間被覆寫i次的和。結束這次循環後sum[cnt[rt]]還要再減去本區間被覆寫大于cnt[rt]次對應的sum
最後如果cnt[rt]=0，i從1到k循環，如果沒有子區間，sum就是0，有的話就是子區間的和
/*
顔色覆寫，多了顔色融合，，
用七個sum去記錄七種顔色，三個cnt記錄三種不同顔色的覆寫
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define maxn 20005
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
#define ll long long
struct Seg{
int x,y1,y2,c;
Seg(){}
Seg(int a,int b,int c,int d):x(a),y1(b),y2(c),c(d){}
bool operator<(const Seg & a)const
{return x<a.x;}
}segs[maxn];
int y[maxn],toty,tot;
int sum[maxn<<2][8],cnt[maxn<<2][4];
map<int,int>mp;
void pushup(int rt,int l,int r){
int tmp=0;
if(cnt[rt][1]) tmp|=1;
if(cnt[rt][2]) tmp|=2;
if(cnt[rt][3]) tmp|=4;
//cout << tmp << endl;
for(int i=0;i<=7;i++)
sum[rt][i]=0;
if(tmp){
sum[rt][tmp]=y[r]-y[l];
for(int i=1;i<=7;i++)
if(l+1!=r && tmp!=(tmp|i)){ //如果有更進階的顔色
sum[rt][tmp|i]+=sum[rt<<1][i]+sum[rt<<1|1][i];
sum[rt][tmp]-=sum[rt<<1][i]+sum[rt<<1|1][i];
}
}
else if(l+1!=r)
for(int i=1;i<=7;i++) sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i];
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l && R>=r){
//cout<<c<<endl;
if(c>0) cnt[rt][c]+=1;
else cnt[rt][-c]-=1;
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=toty=0;
mp.clear();
memset(sum,0,sizeof sum);
memset(cnt,0,sizeof cnt);
}
int main(){
int T,x1,x2,y1,y2,c,n;
char col[5];
cin >> T;
for(int tt=1;tt<=T;tt++){
init();
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s%d%d%d%d",col,&x1,&y1,&x2,&y2);
if(col[0]=='R') c=1;
if(col[0]=='G') c=2;
if(col[0]=='B') c=3;
segs[tot++]=Seg(x1,y1,y2,c);
segs[tot++]=Seg(x2,y1,y2,-c);
y[toty++]=y1,y[toty++]=y2;
}
sort(y,y+toty);
toty=unique(y,y+toty)-y;
for(int i=0;i<toty;i++) mp[y[i]]=i;
sort(segs,segs+tot);
ll res[8]={};
for(int i=0;i<tot;i++){
if(i!=0){
for(int j=1;j<=7;j++)
res[j]+=(ll)(segs[i].x-segs[i-1].x)*sum[1][j];
}
int y1=mp[segs[i].y1];
int y2=mp[segs[i].y2];
update(y1,y2,segs[i].c,0,toty-1,1);
}
printf("Case %d:\n",tt);
printf("%lld\n",res[1]);
printf("%lld\n",res[2]);
printf("%lld\n",res[4]);
printf("%lld\n",res[3]);
printf("%lld\n",res[5]);
printf("%lld\n",res[6]);
printf("%lld\n",res[7]);
}
return 0;
} 轉載于:https://www.cnblogs.com/zsben991126/p/9968122.html