CF1736C2 Good Subarrays (Hard Version)

lingfunny · 2022-10-13 07:49:10 · 题解

对于 C1，有一种做法是固定右端点，设 f_i 为 i 结尾的区间最长为多少，转移方程 f_i=\min(f_{i-1} + 1, a_i)。

我们在这个基础上解决 C2。

假设修改是 (p, x)，那么对于 i < p，f'_i=f_i。（f' 表示修改后的 dp 数组）

如果我们能找到这样一个最小的 q，使得 f'_q = a_q，那么对于 i\ge q 的 f'_i，值是固定的。

所以可以处理出这么一个 g_i，表示钦定 f_i=a_i 时，后缀 f_i 的值。即 g_i=\displaystyle\sum_{j=i}^n f_j。

假设找出了这么一个 q，那么答案可以直接加上 g_q。

还剩下 i\in[p, q) 的 f'_i。因为这部分的 f'_i < a_i，所以有 f'_i=f'_{i-1}+1。

接下来问题是，q 怎么找，g_i 怎么处理。

对于找 q，考虑什么时候 (i, a_i) 可以成为询问 (p, x) 其中一个可行 q，即什么时候会限制询问 (p, x) 的 f'_i 增长。

首先由 f_p=\min(f_{p-1} + 1, x)，我们令 x \gets f_p，那么如果没有限制，f_p\sim f_i 应该为 x, x+1, x+2, x+3, \dots，所以当 x+i-p > a_i 时会产生影响。移项得 x-p > a_i-i。

于是我们把询问 (p, x) 和原数组 (i, a_i) 扔到一起，对于所有二元组 (p, x)，不妨按 x - p 从小到大排序，不断加入限制，查询时直接在所有限制中 upper_bound 即可。

对于计算 g_i，其实也可以用类似计算询问的方法，找到一个最小的 q(q>i)，使得 f_q=a_q，g_i=g_q+S(q-i-1)+(q-i)\times f_{i}。

伪代码如下：

sort ALL by (x - p)
for (p, x, op) in ALL
    if op is ASK
        q = upper_bound(p) in S
        update(op)
    else 
        q = upper_bound(p) in S
        insert p into S
        update(g[p])

// Problem: C2. Good Subarrays (Hard Version)
// URL: https://codeforces.com/contest/1736/problem/C2
// Group: Codeforces - Codeforces Round #825 (Div. 2)
// Time: 2022-10-10 22:36
// Author: lingfunny

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 2e5 + 10;
int q, n, a[mxn], m, f[mxn];
LL S[mxn], res[mxn], pre[mxn], g[mxn];

struct ASK {
    int op, x, p;
} ask[mxn * 2];

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        f[i] = min(f[i - 1] + 1, a[i]);
        S[i] = S[i - 1] + i;
        pre[i] = pre[i - 1] + f[i];
        ask[++m] = { 0, a[i], i };
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i) {
        int p, x;
        scanf("%d%d", &p, &x);
        x = min(x, f[p - 1] + 1);
        ask[++m] = { i, x, p };
    }
    sort(ask + 1, ask + m + 1, [&](const ASK &a, const ASK &b) {
        int wa = a.x - a.p, wb = b.x - b.p;
        if (wa == wb) return a.op > b.op;
        else return wa < wb;
    });
    set<int> ava = { n + 1 };
    for (int i = 1; i <= m; ++i) {
        auto [op, x, p] = ask[i];
        if (!op) {
            q = *ava.upper_bound(p);
            g[p] = g[q] + S[q - p] + (LL)(q - p) * (a[p] - 1);
            ava.insert(p);
        } else {
            q = *ava.upper_bound(p);
            res[op] = pre[p - 1] + S[q - p] + (LL)(q - p) * (x - 1) + g[q];
        }
    }
    for (int i = 1; i <= m - n; ++i) printf("%lld\n", res[i]);
    return 0;
}