离散化,前缀和,差分
一维前缀和和差分之前学过不再记录
二维情况
前缀和
多维前缀和的普通求解方法几乎都是基于容斥原理
例如有这样一个矩阵,可以视为二维数组:
1 2 4 3
5 1 2 4
6 3 5 9
定义一个矩阵\(sum\)使得\(sum_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}a_{i,j}\)那么这个矩阵长这样:
1 3 7 10
6 9 15 22
12 18 29 45
第一个问题是递推求sum的过程,\(sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}\)
因为同时加了\(sum_{i-1,j},sum_{i,j-1}\)重复了\(sum_{i-1,j-1}\)减去
第二个问题是如何应用,譬如求\((x_1,y_1)-(x_2,y_2)\)子矩阵的和
答案\(sum_{x_2,y_2}-sum_{x_1-1,y_2}-sum_{x_2,y_1-1}+sum_{x_1-1,y_1-1}\)
差分
由sum逆推出来,即上述等式改为\(a_{i,j}=sum_{i,j}-sum_{i-1,j}-sum_{i,j-1}+sum_{i-1,j-1}\)
例题
// Problem: Air Cownditioning
// Contest: Virtual Judge - USACO
// URL: https://vjudge.net/problem/USACO-1156
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1e5+10;
int n,a[N],b[N];
LL ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
b[i]-=a[i];
}
for(int i=1;i<=n+1;i++) ans+=max(b[i]-b[i-1],0);
printf("%lld\n",ans);
return 0;
}