建模需要注意下细节，，这是做扫描线的惯例，就是最好把模型建立在笛卡尔坐标系上
剩下的看链接和注释https://blog.csdn.net/shiqi_614/article/details/7983508
/* 扫描线解一个被覆盖了一些面积的区间 问能空余地方能放置多少个1*M或M*1的矩形 设[i,j]为可以作为矩形放置起点的方块，那么只要统计出不能作为起点的方块的面积即可 本题用的是点的行列号，转换成笛卡尔坐标系上的坐标即可 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<map> #define ll long long #define maxn 100005 #define lson l,m,rt<<1 #define rson m,r,rt<<1|1 using namespace std; 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){return x<a.x;} }segs[maxn]; map<int,int>mp; int y[maxn],data[maxn][4],tot,toty; int sum[maxn<<2],flag[maxn<<2]; void pushup(int rt,int l,int r){ if(flag[rt]>0) sum[rt]=y[r]-y[l]; else { if(l+1==r) sum[rt]=0; else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } } 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); } ll solve(int n,int w,int h,int m){ memset(y,0,sizeof y); memset(segs,0,sizeof segs); memset(sum,0,sizeof sum); memset(flag,0,sizeof flag); mp.clear(); tot=toty=0; y[toty++]=1,y[toty++]=h; segs[tot++]=Seg(max(1,w-m),1,h,1); segs[tot++]=Seg(w,1,h,-1); for(int i=0;i<n;i++){ int x1=max(1,data[i][0]-m),y1=data[i][1]; int x2=data[i][2],y2=data[i][3]; segs[tot++]=Seg(x1,y1,y2,1); segs[tot++]=Seg(x2,y1,y2,-1); 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=0; for(int i=0;i<tot;i++){ if(i!=0) res+=(ll)(segs[i].x-segs[i-1].x)*sum[1]; update(mp[segs[i].y1],mp[segs[i].y2],segs[i].c,0,toty-1,1); // cout << res<<endl; } // cout << res << endl <<endl; return res; } int main(){ int w,h,n,m; while(scanf("%d%d%d%d",&w,&h,&n,&m)==4){ for(int i=0;i<n;i++) for(int j=0;j<4;j++){ scanf("%d",&data[i][j]); if(j==2||j==3)data[i][j]++; } ll res1=(ll)(w*h)-solve(n,w+1,h+1,m-1);//把点行列号转换成笛卡尔坐标，即把点扩展成一块单位面积 for(int i=0;i<n;i++){//对换矩形的xy轴坐标 swap(data[i][0],data[i][1]); swap(data[i][2],data[i][3]); } ll res2=(ll)(w*h)-solve(n,h+1,w+1,m-1); //cout << res1 << " " << res2 << endl; if(m!=1) printf("%lld ",res1+res2); else printf("%lld ",res1);//注意这个细节 } return 0; }