样例未过,注释清晰!!
//离散化
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl "\n"
using namespace std;
int n;const int N=1005;
struct node{
int x1,y1,x2,y2;
int lx1,ly1,lx2,ly2;
}a[N];
int sx[2*N],sy[2*N],sxn,syn;
int cf[2*N][2*N];//差分
int qzh[2*N][2*N];//前缀和
int main(){
cin >> n;
for(int i = 1;i <= n;i++){
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
sx[i]=a[i].x1;
sx[i+n]=a[i].x2;
sy[i]=a[i].y1;
sy[i+n]=a[i].y2;
}
sort(sx+1,sx+1+2*n);//排序
sort(sy+1,sy+1+2*n);
sxn = unique(sx+1,sx+1+2*n)-sx-1;//长度,去重
syn = unique(sy+1,sy+1+2*n)-sy-1;//长度,去重
for(int i = 1;i <= n;i++){//对应离散化
a[i].lx1 = lower_bound(sx + 1,sx + sxn,a[i].x1) - sx;
a[i].lx2 = lower_bound(sx + 1,sx + sxn,a[i].x2) - sx;
a[i].ly1 = lower_bound(sy + 1,sy + syn,a[i].y1) - sy;
a[i].ly2 = lower_bound(sy + 1,sy + syn,a[i].y2) - sy;
}
for(int i = 1;i <= n;i++){
//差分
cf[a[i].lx1][a[i].ly2]++;
cf[a[i].lx1][a[i].ly1+1]--;
cf[a[i].lx2][a[i].ly2+1]--;
cf[a[i].lx2+1][a[i].ly1+1]++;
}
for(int i = 1;i <= sxn;i++){
for(int j =1;j <= syn;j++){
qzh[i][j] = qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+cf[i][j];
// cout<<qzh[i][j]<<" ";
}
// cout<<endl;
}
ll ans = 0 ;
for(int i =1;i <= sxn;i++){
for(int j = 1;j <= syn;j++){
if(qzh[i][j]){
ans+=(sx[i]-sx[i-1]) * (sy[i]-sy[i-1]);
}
}
}cout<<ans;
return 0;
}