【算法】前缀和、差分和离散化

前缀和

咕咕咕

差分

咕咕咕

离散化

概念

咕咕咕

例题

P1884 [USACO12FEB]Overplanting S

相当于地毯（P3397）和火烧赤壁（P1496）的二合一。

观察到矩形坐标的范围远大于 $n$ 的范围，于是考虑离散化。

离散化之后变成二维线段覆盖问题，直接暴力枚举相邻的点之间的区域是否被覆盖。

这样可以过，但是程序用时直逼上限，考虑用二维差分优化。

首先离散化，处理出

设 $d[i][j]$为差分数组，则对 $d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

每次覆盖 $(x1,y1)$ 到 $(x2,y2)$ 的矩形时，只需修改 $d[x1][y1]++,d[x1][y2+1]–,d[x2+1][y1]–,d[x2+1][y2+1]++$

但此时下标表示的是点之间的线段，所以 $x2$ 和 $y2$ 需要减一

在修改过后对差分数组求前缀和即可得到每一块地是否被覆盖的信息

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define N 2005

int n,cntx,cnty;
ll ans;
ll X1[N],X2[N],Y1[N],Y2[N],x[2*N],y[2*N];
int f[N][N];

int main(){
	int i,j,k;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		x[2*i-1]=X1[i],x[2*i]=X2[i];
		y[2*i-1]=Y1[i],y[2*i]=Y2[i];
	}
	sort(x+1,x+2*n+1),sort(y+1,y+2*n+1);
	cntx=unique(x+1,x+2*n+1)-x-1,cnty=unique(y+1,y+2*n+1)-y-1;
	
	for(k=1;k<=n;k++){
		int a1=lower_bound(x+1,x+cntx+1,X1[k])-x;
		int a2=lower_bound(x+1,x+cntx+1,X2[k])-x;
		int b1=lower_bound(y+1,y+cnty+1,Y1[k])-y;
		int b2=lower_bound(y+1,y+cnty+1,Y2[k])-y;
		f[a1][b1]++,f[a1][b2]--,f[a2][b1]--,f[a2][b2]++;
	}
	
	for(i=1;i<cntx;i++)
		for(j=1;j<cnty;j++){
			f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
			ans+=(f[i][j]!=0)*(x[i+1]-x[i])*(y[j+1]-y[j]);
		}
	cout<<ans<<endl;
	return 0;
}