CCO2023 Real Mountains

· · 题解

P10067 [CCO2023] Real Mountains

设 b_i=\min(\max_{1\leq j\leq i}\{a_j\},\max_{i\leq j\leq n}\{a_j\})，显然有 b 是一组最小的可达的满足要求的方案。可以证明 b 是唯一的一组方案。所以我们的目标就变为求得最小代价使得 h 变为 b。

容易猜测一个结论：每次选择 h_i 最小且需要增加的位置，然后进行一次操作对其 +1。显然这个结论是正确的，证明可以考虑若存在 h_j>h_i 且 j 的操作在 i 前，两个交换一定不劣。那么如果有若干个 h_i 并列最小值怎么办？

假设这个并列最小值为 x，有 k 个，我们要将这些全部变为 x+1。设最左侧的 x 为 h_l，最右侧的 x 为 h_r。

最优操作方案是：对于左端点，我们找到二元组 (o,p)，满足 h_o>h_l<h_p,o<l<p，且不存在 h_l<h_{o'}<h_o,o'<l，也不存在 h_l<h_{p'}<h_p,p'>l。对于右端点，同理找到一个二元组 (q,r)。

那么可以先进行一次 (o,l,p)，一次 (l,r,q)，(k-2) 次 (l,i,r) 完成目标。总代价为 h_o+h_r+h_p+2k-3+3(k-1)x。若 h_p>h_q，还可以先操作右端点再操作左端点。故最优的总代价为 h_o+\min(h_p,h_q)+h_r+2k-3+3(k-1)x。

所以我们得到了一个暴力做法：遍历整个数组，提取出若干个 还需增加的并列最小值，找到两个二元组进行更新。复杂度爆炸。

考虑离散化。若出现在 h 中且大于最小值 x 的数为 y，则一定会使用相同的两个二元组更新相同数量、位置的 x 一路到 y。所以我们将三元组 (h_i,i,-1),(b_i,i,1) 进行排序然后扫描线，可以将复杂度优化到 O(n^2)。

现在问题转化为了一个序列 h，两种操作：

发现很难处理修改。然而仔细分析可以发现修改是不需要的。因为根据上述算法，不可能存在两个位置 (i,j)，最开始 h_i<h_j，在 中途的某个过程时既有 h_j<b_j 又有 h_i>h_j。所以只用维护查询操作，使用主席树即可。

const int N = 1e6 + 10;
const ll P = 1e6 + 3;
int n;
ll a[N], b[N];
tuple<ll, int, int> q[N*2];
ll ans;

ll Sum(ll x, ll y){
    return (y * (y-1) / 2 % P - x * (x-1) / 2 % P + P) % P;
}

int t[N*100], ls[N*100], rs[N*100];
int rtl[N], rtr[N], cnt;
int add(int p, int l, int r, int x){
    ++ cnt;
    tie(t[cnt], ls[cnt], rs[cnt]) = tie(t[p], ls[p], rs[p]);
    p = cnt;
    if(l == r){
        ++ t[p];
    } else {
        int mid = l + r >> 1;
        if(x <= mid){
            ls[p] = add(ls[p], l, mid, x);
        } else {
            rs[p] = add(rs[p], mid+1, r, x);
        }
        t[p] = t[ls[p]] + t[rs[p]];
    }
    return p;
}
int qry(int p, int l, int r, int ge){
    if(t[p] == 0 || r <= ge){
        return -1;
    } else if(l == r){
        return l;
    } else {
        int mid = l + r >> 1, tmp;
        if((tmp = qry(ls[p], l, mid, ge)) > ge){
            return tmp;
        } else {
            return qry(rs[p], mid+1, r, ge);
        }
    }
}

int qrl(int x, int mn){
    return qry(rtl[x], 1, 1e9, mn);
}
int qrr(int x, int mn){
    return qry(rtr[x], 1, 1e9, mn);
}

void solve(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%lld", &a[i]);
        q[i] = { a[i], i, -1 };
    }
    ll mx = 0;
    rtl[0] = ++ cnt;
    for(int i = 1; i <= n; ++ i){
        mx = max(mx, a[i]);
        rtl[i] = add(rtl[i-1], 1, 1e9, a[i]);
        b[i] = mx;
    }
    mx = 0;
    rtr[n+1] = ++ cnt;
    for(int i = n; i >= 1; -- i){
        mx = max(mx, a[i]);
        b[i] = min(b[i], mx);
        rtr[i] = add(rtr[i+1], 1, 1e9, a[i]);
        q[i+n] = { b[i], i, 1 };
    }
    sort(q + 1, q + n + n + 1);
    set<int> st;
    for(int i = 1; i < n + n; ++ i){
        if(get<2>(q[i]) == -1){
            st.insert(get<1>(q[i]));
        } else {
            st.erase(get<1>(q[i]));
        }
        if(get<0>(q[i]) != get<0>(q[i+1]) && st.size()){
            ll fr = get<0>(q[i]), to = get<0>(q[i+1]);
            ll l = *st.begin(), r = *st.rbegin(), k = st.size();
            ll oo = qrl(l, fr), pp = qrr(l, fr), qq = qrl(r, fr), rr = qrr(r, fr);
            ll p = qrl(l, fr), q = qrr(r, fr);
            if(k == 1){
                ans += Sum(fr, to);
                ans += (oo + pp) % P * (to - fr) % P;
            } else {
                ans += (oo + rr + min(pp, qq) + k + k - 3) % P * (to - fr) % P;
                ans += 3 * (k - 1) % P * Sum(fr, to) % P;
            }
            ans %= P;
        }
    }
    printf("%lld\n", ans);
}