专栏文章

题解：P13963 [ICPC 2023 Nanjing R] 接雨水

SSjdjcook
P13963题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@min2p5vj
此快照首次捕获于
2025/12/01 19:35
3 个月前
此快照最后确认于
2025/12/01 19:35
3 个月前
查看原文

P13963 接雨水

饭菜烧得好，媳妇回家早。
—— fjd

题目描述

给定长度为 nn 的整数序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n，第 ii 次修改会将 axia_{x_i} 的值增加 viv_i。在每次修改之后，计算：
∑i=1n(min⁡(fi,gi)−ai)\sum\limits_{i = 1}^n \left( \min(f_i, g_i) - a_i \right)
其中 fi=max⁡(a1,a2,⋯ ,ai)f_i = \max(a_1, a_2, \cdots, a_i)，gi=max⁡(ai,ai+1,⋯ ,an)g_i = \max(a_i, a_{i + 1}, \cdots, a_n)。

题目分析

如果每次修改都更新并统计答案显然无法通过本题,那么我们考虑...
对和式进行拆分：
有和式你不拆?
sum=∑i=1n(min⁡(fi,gi)−ai)=∑i=1nmin⁡(fi,gi)−∑i=1nai\begin{aligned} sum &= \sum_{i = 1}^{n} (\min(f_i, g_i) - a_i) \\ &= \sum_{i = 1}^{n} \min(f_i, g_i) - \sum_{i = 1}^{n} a_i \end{aligned}
瞪眼法观察到 min⁡(fi,gi)=fi+gi−max⁡(fi,gi)\min(f_i,g_i) = f_i + g_i - \max(f_i, g_i)，可得：
sum=∑i=1nfi+∑i=1ngi−∑i=1nmax⁡(fi,gi)−∑i=1nai\begin{aligned} sum &= \sum_{i = 1}^{n} f_i + \sum_{i = 1}^{n} g_i - \sum_{i = 1}^{n} \max(f_i, g_i) - \sum_{i = 1}^{n} a_i \end{aligned}

重点之一(敲黑板)

  • 前缀最大值 fif_i 单调不降
  • 后缀最大值 gig_i 单调不增
证明：
  • 对于 fif_i：若 fi>fi+1f_i > f_{i+1}，则 fi+1f_{i+1} 应更新为 fif_i，因此 fi+1≥fif_{i+1} \geq f_i
  • 对于 gig_i：同理可证 gi≥gi+1g_i \geq g_{i+1}

选择数据结构维护

观察到 ff 和 gg 都具有区间性质，可以使用 ODT（Old Driver Tree，老司机树）来维护。
此外，∑i=1nmax⁡(fi,gi)\sum_{i = 1}^{n} \max(f_i, g_i) 实际上就是 n×max⁡(a1,a2,⋯ ,an)n \times \max(a_1, a_2, \cdots, a_n)，因为对于每个位置 ii，max⁡(fi,gi)\max(f_i, g_i) 都等于全局最大值一个前缀最大一个后缀最大显然合起来就是全局最大嘛。

时间复杂度

使用 ODT 维护，每次修改的均摊复杂度为 O(log⁡n)O(\log n)，总复杂度 O(nlog⁡n)O(n \log n) 足以通过本题。

关于ODT

ODT 固然是好的,但也不能滥用,相信来做这道题的人也多少了解过一些
什么你说你不知道?
这里给几道板子题: P4145 P13983 和 练手题: P5350 P5251 。
代码实现CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IT set<node>::iterator

const int N = 1e5 + 10, INF = 1e18;

inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) {
        f |= c == '-';
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + (c ^ 48);
        c = getchar();
    }
    return f ? -x : x;
}

struct node {
    int l, r;
    mutable int v;
    bool operator < (const node &x) const {
        return l < x.l;
    }
};

set<node> sf, sg;
int n, q, t, a[N], sum;

IT splf(int pos) {
    IT it = sf.lower_bound({pos, 0, 0});
    if (it != sf.end() && it->l == pos) return it;
    it--;
    int l = it->l, r = it->r;
    int v = it->v;
    sf.erase(it);
    sf.insert({l, pos - 1, v});
    return sf.insert({pos, r, v}).first;
}

IT splg(int pos) {
    IT it = sg.lower_bound({pos, 0, 0});
    if (it != sg.end() && it->l == pos) return it;
    it--;
    int l = it->l, r = it->r;
    int v = it->v;
    sg.erase(it);
    sg.insert({l, pos - 1, v});
    return sg.insert({pos, r, v}).first;
}

IT gtf(int pos) {
    IT it = sf.lower_bound({pos, 0, 0});
    if (it != sf.end() && it->l == pos) return it;
    it--;
    return it;
}

IT gtg(int pos) {
    IT it = sg.lower_bound({pos, 0, 0});
    if (it != sg.end() && it->l == pos) return it;
    it--;
    return it;
}

void chgf(int x) {
    IT itr = gtf(x);
    if (itr->v >= a[x]) return;
    itr = splf(x);
    IT itl = itr;
    for (; itr->v < a[x] && itr != sf.end(); itr++) {
        sum += (itr->r - itr->l + 1) * (a[x] - itr->v);
    }
    itr--;
    int r = itr->r;
    itr++;
    sf.erase(itl, itr);
    sf.insert({x, r, a[x]});
    return;
}

void chgg(int x) {
    IT itr = gtg(x);
    if (itr->v >= a[x]) return;
    itr = splg(x + 1);
    IT itl = itr;
    itr--;
    for (; itr->v < a[x]; itr--) {
        sum += (itr->r - itr->l + 1) * (a[x] - itr->v);
    }
    if (itr->v >= a[x]) itr++;
    else {
        sum += (itr->r - itr->l + 1) * (a[x] - itr->v);
    }
    int l = itr->l;
    sg.erase(itr, itl);
    sg.insert({l, x, a[x]});
    return;
}

void slv() {
    sum = 0;
    n = read();
    int mx = 0, l = 1;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        sum -= a[i];
        if (!mx) mx = a[i];
        if (mx < a[i]) {
            sf.insert({l, i - 1, mx});
            l = i;
            mx = a[i];
        }
    }
    sf.insert({l, n, max(mx, a[n])});
    mx = a[n];
    l = n;
    for (int i = n; i >= 1; i--) {
        if (mx < a[i]) {
            sg.insert({i + 1, l, mx});
            l = i;
            mx = a[i];
        }
    }
    mx = max(a[1], mx);
    sum -= mx * n;
    sg.insert({1, l, mx});

    sf.insert({n + 1, n + 100, INF});
    sg.insert({-1, -100, INF});

    for (IT it = sf.begin(); it->v != INF; it++) {
        sum += (it->r - it->l + 1) * it->v;
    }

    for (IT it = sg.begin(); it != sg.end(); it++) {
        if (it->v == INF) continue;
        sum += (it->r - it->l + 1) * it->v;
    }
    
    int q = read();
    while (q--) {
        int x = read(), c = read();
        a[x] += c; 
        if (mx < a[x]) {
            sum -= (a[x] - mx) * n;
            mx = a[x];
        }
        sum -= c;
        chgf(x);
        chgg(x);
        cout << sum << endl;
    }
    sf.clear();
    sg.clear();
}

signed main() {
    int t = read();
    while (t--) {
        slv();
    }
    return 0;
}

评论

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

正在加载评论...