题解：AT_arc228_b [ARC228B] Minimize Topological Order

zsjaaaxy · 2026-10-21 10:57:10 · 题解

solution

首先我们可以刻画一下题目的限制。相当于 \forall i，如果想要作为子节点连向 j，需要 \max_{j<k<i} p_{k}<p_{i}。

刻画完就好做了吧（事实上我在上一步卡了很久进行了要么不充分要么不必要的刻画）。我们不妨单调栈求出父节点可以选择的区间，然后从中选择最小的，还需要更新选择的代价 a_{i}(2c_{i}+1)。由于需要区间查最值和单点改，使用线段树即可。

补充一下每次选最小值的正确性。发现后面的位置的选择区间要么与当前值的选择区间不交，要么包含当前的区间，所以直接选当前最优解不劣。

时间 O(n\log n)，空间 O(n)。

code

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
const int N=1000000;
int n,p[N],a[N],c[N],ans=0,ll[N];
vector<int> v[N];
stack<int> s;
struct SGT
{
    int tree[N],w[N];
    void build(int x,int l,int r)
    {
        if(l==r)
        {
            w[x]=l;
            tree[x]=a[p[l]];
            return;
        }
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        if(tree[x*2]<tree[x*2+1])
        {
            w[x]=w[x*2],tree[x]=tree[x*2];
        }
        else
        {
            w[x]=w[x*2+1],tree[x]=tree[x*2+1];
        }
        return;
    }
    void update(int x,int l,int r,int qp,int op)
    {
        if(l==r)
        {
            tree[x]=op;
            return;
        }
        if(qp<=mid)
        {
            update(x*2,l,mid,qp,op);
        }
        else
        {
            update(x*2+1,mid+1,r,qp,op);
        }
        if(tree[x*2]<tree[x*2+1])
        {
            w[x]=w[x*2],tree[x]=tree[x*2];
        }
        else
        {
            w[x]=w[x*2+1],tree[x]=tree[x*2+1];
        }
        return;
    }
    pair<int,int> query(int x,int l,int r,int ql,int qr)
    {
        if(ql<=l&&qr>=r)
        {
            return make_pair(tree[x],w[x]);
        }
        pair<int,int> res=make_pair(1e9,0);
        if(ql<=mid)
        {
            res=query(x*2,l,mid,ql,qr);
        }
        if(qr>mid)
        {
            res=min(res,query(x*2+1,mid+1,r,ql,qr));
        }
        return res;
    }
}S;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    //我们单调栈求出可以连的范围，然后怎么办，一定要线段树吗 
    for(int i=n;i>=1;i--)
    {
        while(!s.empty()&&p[s.top()]<p[i])
        {
            ll[s.top()]=i;
            s.pop();
        }
        s.push(i);
    }
    S.build(1,1,n);
    for(int i=2;i<=n;i++)
    {
        if(!ll[i])
        {
            ll[i]=1;
        }
        pair<int,int> g=S.query(1,1,n,ll[i],i-1);
        ans+=g.first;
        c[p[g.second]]++;
        S.update(1,1,n,g.second,a[p[g.second]]*(2*c[p[g.second]]+1));
    }
    cout<<ans;
    return 0;
}