差分求助
查看原帖
差分求助
241115
guzzqq楼主2021/7/21 14:06
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
using namespace std;
int N;
int x11[1011], y11[1011];
int x2[1011], y2[1011];
int a[4011], c[4011];
int delta[4011][4011];
int f[4011][4011];
int cnta, cntc;
long long ans;
int main(){
	scanf("%d",&N);
	rep(i, 1, N){
		scanf("%d%d%d%d",&x11[i], &y11[i], &x2[i], &y2[i]);
		x11[i] += 1e8;y11[i] += 1e8;x2[i] += 1e8;y2[i] += 1e8;
		a[++cnta] = x11[i];a[++cnta] = y11[i];a[++cnta] = x2[i];a[++cnta] = y2[i];
	}
	sort(a + 1, a + 4 * N + 1);
	a[0] = -114514;
	rep(i, 1, 4 * N)if(a[i] != a[i - 1])c[++cntc] = a[i];
	rep(i, 1, N){
		int xx1 = lower_bound(c + 1, c + cntc + 1, x11[i]) - c;
		int yy1 = lower_bound(c + 1, c + cntc + 1, y11[i]) - c;
		int xx2 = lower_bound(c + 1, c + cntc + 1, x2[i]) - c;
		int yy2 = lower_bound(c + 1, c + cntc + 1, y2[i]) - c;
		delta[xx2][yy2]++;
		delta[xx2][yy1 - 1]--;
		delta[xx1 - 1][yy2]--;
		delta[xx1 - 1][yy1 - 1]++;
	}
	rep(i, 1, cntc){
		rep(j, 1, cntc){
		//	printf("%d" ,delta[i][j]);
			f[i][j] = delta[i][j] + delta[i - 1][j] + delta[i][j - 1] - delta[i - 1][j - 1];
			if(f[i][j] != 0 && f[i - 1][j - 1] != 0){
				ans += (long long)((c[i] - c[i - 1]) * (c[j] - c[j - 1]));
			}
		}
	//	printf("\n");
	}
		
	printf("%lld",ans);
	return 0;
}
2021/7/21 14:06
加载中...