题解：P12448 [COTS 2025] 观草 / Trava 题解

· · 题解

考虑阶梯化贡献，即求

\begin{aligned} \sum_{x = 1}^{V} \sum_{i = 1}^{n - k + 1} [\max_{j = i}^{i + k - 1}\{a_j\} >= x] &= \sum_{x = 1}^{V} \sum_{i = 1}^{n - k + 1} [\exist j \in [i, i + k - 1], a_j \geq x]\\ &= \sum_{x = 1}^{V} \sum_{i = 1}^{n - k + 1} V - [\forall j \in [i, i + k - 1], a_j < x]\\ \end{aligned}

如果对于 x，一个极长的 [l, r] 满足 j \in [l, r], a_j < x，那么其对 res_i 贡献 -(r - l - i + 2)，其中 i \leq r - l + 1。我们注意到一次修改即为在 x = a_k + 1 的位置将 [a_k < x] 从 1 变为 0，假设原本包含 k 的极长 a_j < x 区间为 [l, r]，那么将变成 [l, k - 1] 和 [k + 1, r]，使用树状数组维护区间加等差数列，单点查询即可。

我们考虑对于 x，包含 k 的 l, r 分别具有什么意义。我们注意到 l 是最大的 l \leq k，使得 \forall j \in [l, k], a_j < x，r 是最大的 r \geq k，使得 \forall j \in [k, r], a_j < x，这显然使用线段树上二分维护，考虑从根节点走到 k 的路径，如果某个点极深的点走的是右儿子，且其左儿子最大值大于等于 x，那么最大的 l' = l - 1 满足 a_{l'} \geq x 必然在这一左儿子内，在该节点内二分最大的位置即可，r 的处理是类似的。时间复杂度 \mathcal{O}(q\log n)。

我们考虑如何计算初始的答案。设 pl_i 表示最小的位置使得 \forall j \in [pl_i, i], a_j \leq a_i，pr_i 表示最大的位置使得 \forall j \in [i, pr_i], a_j < a_i，那么对于一个 k 的查询和 [i, i + k - 1]，其 max 能取到 a_j 当且仅当 i \in [pl_j, j] 且 i + k - 1 \in [j, pr_j]，即 i \in [pl_j, j] \cap [j - k + 1, pr_j - k + 1]，并且能满足这一条件的 j 显然仅有一个，于是答案即为

\sum_{j = 1}^{n} a_j \times \max\{0, \min\{j, pr_j - k + 1\} - \max\{pl_j, j - k + 1\} + 1\}

考虑 k 变化时后面的系数取得怎样的值，不难注意到该系数为

\begin{cases} k & k < \min\{pr_j - j + 1, j - pl_j + 1\}\\ pr_j - j + 1 & pr_j - j + 1 \leq k < j - pl_j + 1\\ j - pl_j + 1 & j - pl_j + 1 \leq k < pr_j - j + 1\\ pr_j - pl_j - k + 2 & \max\{j - pl_j + 1, pr_j - j + 1\} \leq k \leq pr_j - pl_j + 2\\ 0 & k > pr_j - pl_j + 2\\ \end{cases}

我们发现这些项中有一些和 k 无关的常量，同时还有一些 k，分别开两个差分数组分别维护常量和 k 的系数，差分维护修改后前缀和计算答案即可。

时间复杂度 \mathcal{O}(n + q\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 5e5 + 10;

int n, q;
int a[maxn], pl[maxn], pr[maxn];
long long d1[maxn], d2[maxn], res[maxn];

namespace BIT{
    long long tree1[maxn], tree2[maxn];
    inline int lbw(int x){
        return x & -x;
    }
    inline void add(int x, int k){
        for (int i = x; i; tree1[i] += k, tree2[i] += x * k, i -= lbw(i));
    }
    inline long long query(int x){
        long long res = 0;
        for (int i = x; i <= n; res += tree2[i] - (x - 1) * tree1[i], i += lbw(i));
        return res;
    }
}

using namespace BIT;

namespace segtree{
    struct{
        int l, r, val;
    } tree[maxn << 2];
    inline void build(int index, int l, int r){
        tree[index].l = l, tree[index].r = r;
        if (l == r){
            return tree[index].val = a[l], void();
        }
        const int mid = l + r >> 1;
        build(index << 1, l, mid), build(index << 1 | 1, mid + 1, r), tree[index].val = max(tree[index << 1].val, tree[index << 1 | 1].val);
    }
    inline void modify(int index, int x, int k){
        if (tree[index].l == tree[index].r){
            return tree[index].val = k, void();
        }
        const int mid = tree[index].l + tree[index].r >> 1;
        modify(index << 1 | x > mid, x, k), tree[index].val = max(tree[index << 1].val, tree[index << 1 | 1].val);
    }
    inline pair<int, int> calc(int index, int x, int k){
        if (tree[index].l == tree[index].r){
            return make_pair(0, 0);
        }
        const int mid = tree[index].l + tree[index].r >> 1;
        const pair<int, int> tmp = calc(index << 1 | x > mid, x, k);
        if (x <= mid){
            return tree[index << 1 | 1].val >= k && !tmp.second ? make_pair(tmp.first, index << 1 | 1) : tmp;
        }else{
            return tree[index << 1].val >= k && !tmp.first ? make_pair(index << 1, tmp.second) : tmp;
        }
    }
    inline int fnd1(int index, int k){
        if (tree[index].l == tree[index].r){
            return tree[index].l;
        }
        const int mid = tree[index].l + tree[index].r >> 1;
        return tree[index << 1 | 1].val < k ? fnd1(index << 1, k) : fnd1(index << 1 | 1, k);
    }
    inline int fnd2(int index, int k){
        if (tree[index].l == tree[index].r){
            return tree[index].l;
        }
        const int mid = tree[index].l + tree[index].r >> 1;
        return tree[index << 1].val < k ? fnd2(index << 1 | 1, k) : fnd2(index << 1, k);
    }
}

using namespace segtree;

int main(){
    scanf("%d %d", &n, &q), a[0] = a[n + 1] = 2e9;
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        for (pl[i] = i - 1; pl[i] && a[pl[i]] < a[i]; pl[i] = pl[pl[i]]);
    }
    build(1, 0, n + 1);
    for (int i = n; i; i--){
        for (pr[i] = i + 1; pr[i] && a[pr[i]] <= a[i]; pr[i] = pr[pr[i]]);
    }
    for (int i = 1; i <= n; i++){
        pl[i]++, pr[i]--;
        long long x = i - pl[i] + 1, y = pr[i] - i + 1;
        x > y && (swap(x, y), 1538), d2[1] += a[i], d2[x] -= a[i], d1[x] += a[i] * x, d1[y] += y * a[i], d1[x + y + 1] -= (x + y) * a[i], d2[y] -= a[i], d2[x + y + 1] += a[i];
    }
    for (int i = 1; i <= n; i++){
        d1[i] += d1[i - 1], d2[i] += d2[i - 1], res[i] = d1[i] + d2[i] * i;
    }
    while (q--){
        char op[10];
        int x;
        scanf("%s %d", op, &x);
        if (op[0] == '?'){
            printf("%lld\n", res[x] + query(x));
        }else{
            modify(1, x, ++a[x]);
            const pair<int, int> pos = calc(1, x, a[x]);
            const int l = fnd1(pos.first, a[x]) + 1, r = fnd2(pos.second, a[x]) - 1;
            add(r - l + 1, 1), add(x - l, -1), add(r - x, -1);
        }
    }

return 0;
}