前缀和

一维前缀和：

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;
}