Delicious Problem: AT_arc228_b

FantasySegmentTree · 2026-10-21 14:46:03 · 题解

标有 Delicious Problem 标号的题目将有 Hint 题解。这种题目适合一步步品尝。

:::info[Hint 1] 如果没有字典序的要求，那么对于给定的序列，你能否给出一个构造 T 的方式，使得当前序列是其代价最小的序列？（仔细理解一下这个问题） :::

:::success[Answer 1] 这当然可以了。

首先根节点不用说。对于每个非根节点 v，考虑怎样的代价最小。设 v 的父亲为 u，原来 u 的孩子个数为 c_u，则新增代价为 a_u(c_u+1)^2 - a_uc_u^2=a_u(2c_u+1)，只需要找到 a_u(2c_u+1) 最小的点即可。

:::

:::info[Hint 2] 考虑一下，如果加入了字典序的要求，会有什么变化？ :::

:::success[Answer 2] 设当前遍历到 p_i。考虑任意的 p_j(j>i)。如果 p_j > p_i，那么没什么影响，可能是字典序导致的。但是如果 p_j < p_i，那就说明 p_j 受到了前面某个节点 p_k 的约束（不一定是 p_i），也即 p_j 在 p_k 的子树内，使其无法往前。显然，p_j 只会受到最大的 k<j 且 p_k > p_j 的节点的约束，因为更前面的节点无法说明一定是它导致的逆序。

:::info[Hint 3] 怎么把前两个 Hint 提供的信息结合起来？ :::

:::success[Answer 3] 你会发现 p_j 父亲的取值是在 p 的一个区间里的，那直接用线段树维护区间最小值及其标号，并进行更新就可以了。 :::

:::success[Code]

#include <iostream>
#define N 200005
using namespace std;

typedef long long ll;

ll n, p[N], a[N], c[N], top;

ll st[N];

struct node {
    ll l, r, minn, mink;
}b[N << 2];

void push_up(ll x) {
    b[x].minn = min(b[x << 1].minn, b[x << 1 | 1].minn);
    if(b[x << 1].minn < b[x << 1 | 1].minn) b[x].mink = b[x << 1].mink;
    else b[x].mink = b[x << 1 | 1].mink;
}

void build(ll l, ll r, ll x) {
    b[x].l = l, b[x].r = r;
    if(l == r) {
        b[x].minn = a[p[l]];
        b[x].mink = l;
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    push_up(x);
}

void change(ll id, ll k, ll x) {
    if(b[x].l > id || b[x].r < id) return;
    if(b[x].l == b[x].r) {
        b[x].minn = k;
        return;
    }
    change(id, k, x << 1);
    change(id, k, x << 1 | 1);
    push_up(x);
}

pair <int, int> query(ll l, ll r, ll x) {
    if(b[x].l >= l && b[x].r <= r) return make_pair(b[x].minn, b[x].mink);
    ll mid = (b[x].l + b[x].r) >> 1;
    if(r <= mid) return query(l, r, x << 1);
    else if(l > mid) return query(l, r, x << 1 | 1);
    else {
        pair <int, int> lx = query(l, r, x << 1), rx = query(l, r, x << 1 | 1), nx;
        nx.first = min(lx.first, rx.first);
        if(lx.first < rx.first) nx.second = lx.second;
        else nx.second = rx.second;
        return nx;
    } 
}

int main() {
    cin >> n;
    for(ll i = 1; i <= n; i++) cin >> p[i];
    for(ll i = 1; i <= n; i++) cin >> a[i];
    build(1, n, 1);
    st[++top] = 1;
    ll ans = 0;
    for(ll i = 2; i <= n; i++) {
        ll cs = 1;
        while(top && p[st[top]] < p[i]) top--;
        if(top) cs = st[top];
        st[++top] = i;
        pair <int, int> sr = query(cs, i - 1, 1);
        ans += sr.first;
        ll t = sr.second;
        c[p[t]]++;
        change(t, a[p[t]] * (2 * c[p[t]] + 1), 1);
    }
    cout << ans;
}

:::