题解：P10067 [CCO 2023] Real Mountains

· · 题解

前言：做模拟赛没做出来。

solution

首先考虑最后的形态，一定是先单调不降，后单调不升。

可以计算出每个点的最终值为它前面出现过的最大值和后面出现过的最大值的最小值。

然后发现先操作较小的一定不劣，较大的一定不会用较小的，但较小的有可能用到较大的。

根据当前较小值所在的位置个数分类讨论一下。

如果只有一个，直接用它左边的大于它的最小值和右边的大于它的最小值就可以了，因为我们发现肯定是从最小的开始操作，所以其实就是左边最小值和右边最小值。

考虑两个以上。

先来考虑对于一个高为 h 的位置，它肯定希望它的花费为来源大概为 (h + 1) + h + (h + 1)，所以对于有两个以上的位置，我们可以考虑将最左和最右的位置找出来，先将它们加一，这样中间的所有都一定是最小的花费。

但是这两个怎么算花费也是有讲究的，我们发现你可以先将其中一个加一，然后另一个的其中一边贡献就变成 h + 1 了，这样做就是最优的，然后就是推式子的事情了。

现在我们把整个过程以及细节补全。

先算出来每个位置最终的高度。

对高度离散化，然后我们可以对它本来的高度和最终的高度都将这个位置塞进去。

从小高度到大高度遍历所在位置。

统计出现次数，如果是第一次出现，就说明是初始高度，需要计算花费，我们可以直接在线段树上将这个位置设为正无穷，因为一定不会用到这个位置了，而且这样子直接在线段树上查最小值就是正确的，并把它加入集合里。

如果是第二次出现，那么就说明，已经到达目标位置了，直接将它从集合中删除。

然后依照上面的分讨算花费就可以了，复杂度保证。

code

#include <bits/stdc++.h>

#define int long long

#define INF 1e9

using namespace std;

const int mod = 1e6 + 3;
const int N = 1e6 + 10;

int n, len, ans;

int h[N], H[N], lh[N], rh[N], eh[N];

struct SegmentTree {
    int t[N << 2];

    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define mid ((l + r) >> 1)

    inline void pushup (int p) {
        t[p] = min (t[ls], t[rs]);
    }

    inline void build (int p, int l, int r) {
        if (l == r) return t[p] = h[l], void ();
        build (ls, l, mid), build (rs, mid + 1, r), pushup (p);
    } 

    inline void update (int p, int l, int r, int x) {
        if (l == r) return t[p] = INF, void ();
        x <= mid ? update (ls, l, mid, x) : update (rs, mid + 1, r, x), pushup (p);
    }

    inline int query (int p, int l, int r, int L, int R) {
        if (l > R or r < L or L > R) return INF;
        if (L <= l and r <= R) return t[p];
        return min (query (ls, l, mid, L, R), query (rs, mid + 1, r, L, R)); 
    }

    #undef ls
    #undef rs
    #undef mid
} seg;

vector <int> p[N];

bool vis[N];

signed main () {
    ios :: sync_with_stdio (false), cin.tie (0), cout.tie (0);

    cin >> n;
    for (int i = 1; i <= n; ++ i) 
        cin >> h[i], H[i] = h[i]; 

    int lmax = 0, rmax = 0;
    for (int i = 1; i <= n; ++ i)
        lmax = max (lmax, h[i]), lh[i] = lmax; 
    for (int i = n; i >= 1; -- i)
        rmax = max (rmax, h[i]), rh[i] = rmax;
    for (int i = 1; i <= n; ++ i)
        eh[i] = min (lh[i], rh[i]);

    seg.build (1, 1, n); 

    sort (H + 1, H + 1 + n), len = unique (H + 1, H + 1 + n) - H - 1;

    for (int i = 1; i <= n; ++ i)
        p[lower_bound (H + 1, H + 1 + len, h[i]) - H].push_back (i), p[lower_bound (H + 1, H + 1 + len, eh[i]) - H].push_back (i);

    set <int> s;

    for (int i = 1; i < len; ++ i) {
        for (int j : p[i]) 
            if (vis[j]) s.erase (j);
            else s.insert (j), seg.update (1, 1, n, j), vis[j] = 1;

        if (!s.size ()) continue;

        if (s.size () == 1) {
            int pos = *s.begin (), l = seg.query (1, 1, n, 1, pos - 1), r = seg.query (1, 1, n, pos + 1, n);
            ans = (ans + (H[i + 1] - H[i]) * (l + r) % mod + (H[i + 1] - H[i]) * (H[i + 1] + H[i] - 1) / 2 % mod) % mod;
            continue;
        } 

        int l = *s.begin (), r = *s.rbegin ();
        int mid = seg.query (1, 1, n, l + 1, r - 1);
        l = seg.query (1, 1, n, 1, l - 1), r = seg.query (1, 1, n, r + 1, n);
        ans = (ans + (H[i + 1] - H[i]) * (l + r + min (mid, min (l, r))) % mod + ((s.size () << 1) - 3) * ((H[i] + H[i + 1] + 1) * (H[i + 1] - H[i]) / 2 % mod) % mod + s.size () * ((H[i] + H[i + 1] - 1) * (H[i + 1] - H[i]) / 2 % mod) % mod) % mod;
    }

    cout << ans << endl;

    return 0; 
}