蒟蒻求调!!注释清晰!!!
查看原帖
蒟蒻求调!!注释清晰!!!
768530
Expert_Dream楼主2023/9/8 11:16

样例未过,注释清晰!!

//离散化
#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;
}
2023/9/8 11:16
加载中...