# 前缀和

一维前缀和：

s[i] = s[i - 1] + a[i]

数列 a 中任意$\text [l, r]$ 的和为 s[r] - s[l - 1]

二维前缀和：

s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

求以$\text (x1, y1)$ 为左上角，$\text (x2, y2)$ 为右下角的子矩阵元素和 s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

# 差分

差分序列的前缀和序列就是原序列，利用差分数组将 “区间操作” 变成 “单点操作”

一维差分数组：

dp[i] = a[i] - a[i - 1]

把 a 数组的 [l, r] 上的每个数加上 c，则 dp[l] += c, dp[r + 1] -= c;

对差分数组求前缀和 a[i] = dp[i] + a[i - 1]

二维差分数组：

dp[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

把矩阵中左上角为$\text a[x1][y1]$ 右下角为$\text a[x2][y2]$ 的小矩形中每个元素加上 c，则

1
2
3
4

dp[x1][y1] += c;
dp[x1][y2 + 1] -= c;
dp[x2 + 1][y1] -= c;
dp[x2 + 1][y2 + 1] += c;

对差分矩阵求前缀和得原矩阵

即 a[i][j] = dp[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

# 应用

1. 利用差分，相当求让差分数组 d，从$d[2]$ 到$d[n]$ 全部为 0 的最少步数
2. 从$i$ 到$j$ 进行加 c 的操作共有三种情况
   1. $2\leq i,j\leq n$，那么$d[i]+=c,d[j+1]-=c$
   2. $i=1,2\leq j\leq n$，那么$d[j+1]-=c$
   3. $2\leq i<n,j=n+1$，那么$d[i]+=c$
3. 求出从$d[2]$ 到$d[n]$ 中正数的和 a 以及负数的和 b，共可以进行$min(a,b)$ 次的 1 操作，剩余的$|a-b|$ 次可以进行 2/3 操作
4. 因为队列的情况等价于求$d[1]$ 有多少中情况，那么根据 2/3 的操作，可以让$b[1]$ 加 / 减 0,1,2，……，$|a-b|$，共$|a-b|+1$ 种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll a[N], d[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], d[i] = a[i] - a[i - 1];
    ll a = 0, b = 0;
    for(int i = 2; i <= n; i++)
        if(d[i] < 0) a -= d[i];
        else if(d[i] > 0) b += d[i];
    cout << min(a, b) + abs(a - b) << '\n' << abs(a - b) + 1;
    return 0;
}