专栏文章

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

CClaire0918
P12448题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimz74s0
此快照首次捕获于
2025/12/01 17:57
3 个月前
此快照最后确认于
2025/12/01 17:57
3 个月前
查看原文
考虑阶梯化贡献，即求
∑x=1V∑i=1n−k+1[max⁡j=ii+k−1{aj}>=x]=∑x=1V∑i=1n−k+1[∃j∈[i,i+k−1],aj≥x]=∑x=1V∑i=1n−k+1V−[∀j∈[i,i+k−1],aj<x]\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}
如果对于 xx，一个极长的 [l,r][l, r] 满足 j∈[l,r],aj<xj \in [l, r], a_j < x，那么其对 resires_i 贡献 −(r−l−i+2)-(r - l - i + 2)，其中 i≤r−l+1i \leq r - l + 1。我们注意到一次修改即为在 x=ak+1x = a_k + 1 的位置将 [ak<x][a_k < x] 从 11 变为 00，假设原本包含 kk 的极长 aj<xa_j < x 区间为 [l,r][l, r]，那么将变成 [l,k−1][l, k - 1] 和 [k+1,r][k + 1, r]，使用树状数组维护区间加等差数列，单点查询即可。
我们考虑对于 xx，包含 kk 的 l,rl, r 分别具有什么意义。我们注意到 ll 是最大的 l≤kl \leq k，使得 ∀j∈[l,k],aj<x\forall j \in [l, k], a_j < x，rr 是最大的 r≥kr \geq k，使得 ∀j∈[k,r],aj<x\forall j \in [k, r], a_j < x，这显然使用线段树上二分维护，考虑从根节点走到 kk 的路径，如果某个点极深的点走的是右儿子，且其左儿子最大值大于等于 xx，那么最大的 l′=l−1l' = l - 1 满足 al′≥xa_{l'} \geq x，必然在这一儿子内，在该节点内二分最大的位置即可，rr 的处理是类似的。时间复杂度 O(qlog⁡n)\mathcal{O}(q\log n)。
我们考虑如何计算初始的答案。设 plipl_i 表示最小的位置使得 ∀j∈[pli,i],aj≤ai\forall j \in [pl_i, i], a_j \leq a_i，pripr_i 表示最大的位置使得 ∀j∈[i,pri],aj<ai\forall j \in [i, pr_i], a_j < a_i，那么对于一个 kk 的查询和 [i,i+k−1][i, i + k - 1]，其 max 能取到 aja_j 当且仅当 i∈[plj,j]i \in [pl_j, j] 且 i+k−1∈[j,prj]i + k - 1 \in [j, pr_j]，即 i∈[plj,j]∩[j−k+1,prj−k+1]i \in [pl_j, j] \cap [j - k + 1, pr_j - k + 1]，并且能满足这一条件的 jj 显然仅有一个，于是答案即为
∑j=1naj×max⁡{0,min⁡{j,pjj−k+1}−max⁡{plj,j−k+1}+1}\sum_{j = 1}^{n} a_j \times \max\{0, \min\{j, pj_j - k + 1\} - \max\{pl_j, j - k + 1\} + 1\}
考虑 kk 变化时后面的系数取得怎样的值，不难注意到该系数为
{kk<min⁡{prj−j+1,j−plj+1}prj−j+1prj−j+1≤k<j−plj+1j−plj+1j−plj+1≤k<prj−j+1prj−plj−k+2max⁡{j−plj+1,prj−j+1}≤k≤prj−plj+20k>prj−plj+2\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}
我们发现这些项中有一些和 kk 无关的常量，同时还有一些 kk，分别开两个差分数组分别维护常量和 kk 的系数，差分维护修改后前缀和计算答案即可。
时间复杂度 O(n+qlog⁡n)\mathcal{O}(n + q\log n)。
Code：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...