处理的技巧：差分（一）

树状数组维护差分序列

差分的性质
$b_i$ 为原序列 $a_i$ 的差分序列，则

$$b_i= \begin{cases} a_i - a_{i-1} && i \in [2, n] \\ a_1 && i = 1 \end{cases}$$

• 差分序列的前缀和等于原序列

  $$a_i = \sum_{j = 1}^{i} b_j$$

Acwing242
根据差分序列的性质，我们用树状数组维护差分序列

• 初始化树状数组，$\textbf{tr}[i] = A[i] - A[i-1]$
  $\textbf{add}(i, A_i-A_{i-1})$
• 区间 $[l, r] + d$ （区间内所有的数都加 $d$）
  $\textbf{add}(l, d), \textbf{add}(r+1, -d)$
• 询问修改后下标为 $x$ 的值，执行
  $\textbf{sum}(x)$

const int maxn = 100000 + 10;
ll a[maxn], tr[maxn];
int n, m;

void add(int x, int d) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

ll sum(int x) {
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    // prework
    for (int i = 1; i <= n; i++) add(i, a[i]-a[i-1]);

    // solve
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'Q') {
            int x;
            scanf("%d", &x);
            printf("%lld\n", sum(x));
        }
        else {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            add(l, d), add(r+1, -d);
        }
    }
}

差分序列维护原序列部分和

$a_x$ 的前缀和 $S = \sum_{i=1}^{x} a_i$
如果用差分数组来维护

$$S = \sum_{i=1}^{x} \sum_{j=1}^{i} b_j = \sum_{i=1}^{x} (x-i+1)\cdot b_i$$

也就是说

$$S(x) = (x+1) \sum_{i=1}^{x} b_i - \sum_{i=1}^{x} i \cdot b_i$$

• 用两个树状数组 $\textbf{tr1}, \textbf{tr2}$ 分别维护序列
  $\{b_i\}, \{ib_i\}$
• $[l, r] + d$，转为单点增加
  $\textbf{add}(\textbf{tr1}, l, d)$， $\textbf{add}(\textbf{tr1}, r+1, -d)$
  $\textbf{add}(\textbf{tr2}, l, l\cdot d)$， $\textbf{add}(\textbf{tr2}, r+1, -(r+1)\cdot d)$
• $[l, r]$ 部分和，根据表达式 $S(r)-S(l-1)$
  $S(r) = (r+1) \cdot \textbf{sum}(\textbf{tr1}, r) - \textbf{sum}(\textbf{tr2}, r)$

Acwing243

const int maxn = 100000 + 10;
ll tr1[maxn], tr2[maxn], a[maxn];
int n, m;

void add(ll tr[], int x, ll d) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

ll sum(const ll tr[], int x) {
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

ll S(int x) {
    return (x+1) * sum(tr1, x) - sum(tr2, x);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    // prework
    for (int i = 1; i <= n; i++) {
        add(tr1, i, a[i]-a[i-1]);
        add(tr2, i, i * (a[i]-a[i-1]));
    }

    // solve
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'Q') {
            int l, r;
            scanf("%d%d", &l, &r);
            ll res = S(r) - S(l-1);
            printf("%lld\n", res);
        }
        else {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            add(tr1, l, d), add(tr1, r+1, -d);
            add(tr2, l, (ll)l*d), add(tr2, r+1, -(ll)(r+1)*d);
        }
    }
}

线段树维护差分序列

区间最大公约数问题

$$\begin{gathered} \textbf{gcd}(x_1, x_2) = \textbf{gcd}(x_1, x_2 - x_1) \\ \textbf{gcd}(x_l, x_{l+1}, x_{l+2} \cdots x_n) = \textbf{gcd}(x_l, x_{l+1}-x_l, x_{l+2}-x_{l+1} \cdots ) \end{gathered}$$

• 算法设计

  $$\begin{gathered} \textbf{gcd}(\cdots) \quad \text{线段树维护} \\ [x_l\cdots x_r] + d \quad \text{树状数组维护} \end{gathered}$$

• 初始化，令 $b_i = a_i - a_{i-1}$
  • 对差分序列 $b[1\cdots n]$ 建立线段树维护 $\textbf{gcd}$
  • 同时初始化树状数组 $\textbf{add}(tr[\cdots], i, b_i)$
• 对于命令 $C \ l \ r \ d$ 用线段树和树状数组同步维护
  • 树状数组 $\textbf{add}(l, d), \ \textbf{add}(r+1, -d)$
  • 线段树 $\textbf{change}(1, l, d), \ \textbf{change}(1, r+1, -d)$
• 对于命令 $Q \ l \ r$
  $a_l = \textbf{sum}(l), res \leftarrow \textbf{query}(1, l+1, r)$
  $\textbf{gcd}(a_l, res)$
• 坑点，执行 $[l, r] + d$ 的时候，边界条件是 $b_{n+1} - d$
  建线段树的时候，是根据区间 $[1, n+1]$ 来建立线段树

const int maxn = 500000 + 10;
ll a[maxn], b[maxn];
int n, m;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll tr[maxn];
void add(int x, ll d) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}
ll sum(int x) {
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

class A {
public:
    int l, r;
    ll val;
} t[maxn<<2];

void build(int p, int l, int r) {
    t[p].l = l; t[p].r = r;
    if (l == r) {
        t[p].val = b[l];
        return;
    }
    int mid = (l+r) >> 1;
    if (l <= mid) build(p<<1, l, mid);
    if (r > mid) build(p<<1 | 1, mid + 1, r);

    t[p].val = gcd(t[p<<1].val, t[p<<1 | 1].val);
}


void change(int p, int x, ll d) {
    if (x == t[p].l && t[p].r == x) {
        t[p].val += d;
        return;
    }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) change(p<<1, x, d);
    if (x > mid) change(p<<1 | 1, x, d);
    t[p].val = gcd(t[p<<1].val, t[p<<1 | 1].val);
}

ll query(int p, const int l, const int r) {
    if (l > r) return 0;
    if (l <= t[p].l && t[p].r <= r) return t[p].val;

    int mid = (t[p].l + t[p].r) >> 1;
    ll res = 0;
    if (l <= mid) res = gcd(res, query(p<<1, l, r));
    if (r > mid) res = gcd(res, query(p<<1 | 1, l, r));
    return res;
}

void prework() {
    for (int i = 1; i <= n; i++) {
        add(i, b[i]);
    }
    build(1, 1, n+1);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i-1];

    // use tr[...] and seg-tree
    prework();

    // solve command
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'Q') {
            int l, r;
            scanf("%d%d", &l, &r);
            ll res = query(1, l+1, r);
            ll al = sum(l);
            res = gcd(al, res);
            printf("%lld\n", abs(res));
        }
        else {
            int l, r;
            ll d;
            scanf("%d%d%lld", &l, &r, &d);
            change(1, l, d); change(1, r+1, -d);
            add(l, d); add(r+1, -d);
        }
    }
}

差分 dp

dp 中的背包模型

背包问题中容易混淆的是 0-1背包和完全背包
0-1背包和完全背包，dp阶段的更新方式分别如左右两图所示

• $\textbf{0-1} \ \textbf{背包}$

  • $$f(i, j) = \max \begin{cases} f(i-1, j) && \text{不选第} \ i \ \text{个物品} \\ f(i-1, j-V_i) + W_i \quad V_i \leqslant j < n && \text{选择第} \ i \ \text{个物品} \end{cases}$$

  • $i$ 阶段只与第 $i-1$ 阶段有关，所以可以滚动更新
    $\{i-1\} \to \{i\}$
  • $\textbf{for} \ \forall j = n \ \textbf{downto} \ V_i$

• $\textbf{完全背包}$

  • 状态转移

    $$f(i, j) = \max \begin{cases} f(i-1, j) && \text{第} \ i \ \text{种物品一个都不选} \\ f(i, j-V_i) + W_i \quad V_i \leqslant j < n && \text{继续选第} \ i \ \text{种物品} \end{cases}$$

  • 同样可以滚动更新，此时阶段的变化是
    $\{i\} \to \{i\}$，用当前的阶段更新当前
  • $\textbf{for} \ \forall j = V_i \ \textbf{to} \ n$

差分算法解决 dp 问题

Problem Scores
问题简述
序列中有 $n$ 个元素，满足 $A_1 \leqslant A_2 \leqslant \cdots \leqslant A_n$
从中选取任意 $k$ 个元素，他们的和为 $\sum_{k} a[\cdots]$
从中选取任意 $k+1$ 个元素，他们的和为 $\sum_{k+1} a[\cdots]$
必须保证 $\sum_{k} a[\cdots] < \sum_{k+1} a[\cdots]$，求满足条件的方案数

注意到此时 $A_1 \leqslant A_2 \leqslant \cdots \leqslant A_n$
所以原问题可以转换成为

$$\sum_{i=1}^{k+1} a_i \geqslant \sum_{i=n-k+1}^{n} a_i$$

先证明一个性质，如果 $n-k+1 = k+1$，即 $k = \lfloor \frac{n}{2}\rfloor$ 满足
则对所有的 $1 \leqslant k \leqslant n-1$ 均满足
证明如下

问题转换为满足

$$\sum_{i=1}^{k+1} a_i \geqslant \sum_{i=n-k+1}^{n} a_i \quad (k = \left \lfloor \frac{n}{2} \right \rfloor)$$

• 构造差分序列 $x_i= a_i - a_{i-1}$
  令 $x_0 = 1$，这是因为得分不能为 $0$，可能所有题目得分都是一样的
  此时 $\sum_{i=1}^{n} x_i = 0$ 不满足题意
  所以令 $x_0 = 1$，则此时 $a_n \geqslant 1$ 成立

  $$a_n = 1 + \left(\sum_{i = 1}^{n}x_i \right)$$

• $\left \lfloor \frac{n}{2} \right \rfloor = \frac{n-1}{2}$

  $$\begin{gathered} \sum_{i=1}^{\frac{n+1}{2}} a_i \geqslant \sum_{i = \frac{n+1}{2} + 1}^{n} a_i \\ \Rightarrow \ 2 \left(\sum_{i=1}^{\frac{n+1}{2}} a_i \right)\geqslant \sum_{i = 1}^{n} a_i \\ \Rightarrow 2 \sum_{i=1}^{\frac{n+1}{2}} \left( \frac{n+1}{2} - i + 1 \right) x_i \geqslant \sum_{i=1}^{n}(n-i+1)x_i \end{gathered}$$

  移项，上式可以写成
  $\sum_{i = 1}^{n} C_i\cdot x_i \leqslant 0$

  $$C_i = \begin{cases} n-i+1 && i > \frac{n+1}{2} \\ i-2 && i \leqslant \frac{n+1}{2} \end{cases}$$

• $\left \lfloor \frac{n}{2} \right \rfloor = \frac{n}{2}$
  同理可以求出

  $$\begin{gathered} 2 \left( \sum_{i=1}^{\frac{n}{2}}a_i \right) \geqslant \left( \sum_{i=1}^{n} a_i \right) - a_{\frac{n}{2} + 1} \\ 2\left( \sum_{i=1}^{\frac{n}{2}} \left(\frac{n}{2} - i+1 \right) x_i \right) \geqslant \sum_{i=1}^{n}\left( n-i+1 \right)x_i - \sum_{i=1}^{\frac{n}{2}+1} x_i \end{gathered}$$

  写成如下形式
  $\sum_{i=1}^{n}C_i \cdot x_i \leqslant 0$

  $$C_i = \begin{cases} n-i && i = \frac{n}{2} + 1 \\ n-i+1 && i > \frac{n}{2} + 1 \\ i-2 && i \leqslant \frac{n}{2} \end{cases}$$

  注意到 $i=\frac{n}{2} + 1$ 时候，此时 $i-2=n-i$
  综上所述

  $$C_i = \begin{cases} n-i+1 && i > \left\lfloor \frac{n}{2} \right\rfloor + 1 \\ i-2 && i \leqslant \left\lfloor \frac{n}{2} \right\rfloor + 1 \end{cases}$$

• 问题转换为满足以下条件

  $$\begin{cases} \sum_{i =1}^{n} C_i x_i \leqslant 0 \\ 1 + \left( \sum_{i=1}^{n}x_i \right) \leqslant n \end{cases}$$

  合法的 $x_i$ 取值方案数（注意此时 $x_i$ 未知），其中

  $$C_i = \begin{cases} n-i+1 && i > \left\lfloor \frac{n}{2} \right\rfloor + 1 \\ i-2 && i \leqslant \left\lfloor \frac{n}{2} \right\rfloor + 1 \end{cases}$$

  这是一个线性约束条件，对 $i$ 归纳，只要 $x_1$ 满足约束
  可以递推出其余的 $x_2 \cdots x_n$ 方案

  化简得到

  $$\begin{cases} x_1 \leqslant (n-1) - \left( \sum_{i=2}^{n} x_i \right) \\ x_1 \geqslant \sum_{i=2}^{n} C_ix_i \end{cases}$$

  将不等式看作关于 $x_1$ 取值区间的两个端点，$x_1$ 能取的值一共有

  $$\textbf{cnt} = \max\left( 0, n - \sum_{i=2}^{n}(C_i + 1)x_i \right)$$

• 这个问题可以用 $O(n^2)$ 的 dp 解决
  假设满足 $\sum_{i=2}^{n}\left( C_i+1 \right) x_i = P$，此时对于$\{x_i\}$ 序列，合法的方案数有 $f(P)$ 个
  （注意此时 $x_i$ 未知）
  则最后的答案是
  $(n-P) \cdot f(P), \quad P = \sum V_ix_i \quad (V_i = C_i+1)$

  • $f(P)$ 可以通过完全背包的刷表法解决
    $f(P) = \sum_{i=2}^{n} (C_i+1)x_i$，此时背包的物品种类 $i \in [2, n]$
    每一种物品的个数 $x_i$ 未知，但每一种物品可以重复选
    第 $i$ 种物品的体积为 $V_i = C_i+1$
    $\sum V_ix_i = P$ 其实相当于背包的容积为 $P$，$P \in [0 \cdots n]$，对于第 $i$ 阶段递推式
    $P \in [V_i\cdots n]$
  • $f(i,P) \leftarrow f(i,P) + f(i, P-V_i), \quad P\in [V_i \to n]$
    $f(0) = 1$，此时我们有 $\forall i, \ x_i = 0$

const int maxn = 5000 + 10;
int n, m, C[maxn];
ll f[maxn];

void prework() {
    for (int i = 1; i <= n; i++) {
        int mid = n / 2;
        if (i > mid + 1) C[i] = n-i+2;
        else C[i] = i-1;
    }
}

void dp() {
    memset(f, 0, sizeof f);
    f[0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = C[i]; j <= n; j++) {
            f[j] = (f[j] + f[j-C[i]]) % m;
        }
    }

    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + 1ll * (n-i) * f[i]) % m;

    }
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // prework
    prework();
    // dp
    dp();
}