油漆面积--二维差分求区间变化

1.范围小于1e4,用二维差分可以

2.大于就得用扫描线，参考该题题解

区间和用前缀和，区间变化用差分，差分反应面积合并真的好用，如棋盘

3.范围允许暴力也要想到

https://www.luogu.com.cn/problem/P8648

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n;
int df[10005][10005];
ll s; 
int a[10005][10005];
int ax,ay;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;while(n--){int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;ax=max(ax,x2+1);ay=max(ay,y2+1);df[x1+1][y1+1]++;df[x1+1][y2+1]--;df[x2+1][y1+1]--;df[x2+1][y2+1]++;		}for(int i=0;i<=ax;i++){for(int j=0;j<=ay;j++){if(i-1>=0&&j-1>=0)df[i][j]=df[i-1][j]+df[i][j-1]-df[i-1][j-1]+df[i][j];if(j-1<0){if(i-1>=0) df[i][j]=df[i-1][j]+df[i][j];else df[i][j]=df[i][j];}if(i-1<0){if(j-1>=0) df[i][j]=df[i][j-1]+df[i][j];else df[i][j]=df[i][j];}if(df[i][j]>=1) s++;}}cout<<s;return 0;
}