CodeForces - 1295E Permutation Separation

传送门：CodeForces - 1295E

题目描述

You are given a permutation $p_1,p_2,…,p_n$ （an array where each integer from 1 to n appears exactly once）. The weight of the i-th element of this permutation is $a_i$.

At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements $p_1,p_2,…,p_k$, the second — $p_{k+1},p_{k+2},…,p_n$, where $1≤k<n$.

After that, you may move elements between sets. The operation you are allowed to do is to choose some element of the first set and move it to the second set, or vice versa （move from the second set to the first）. You have to pay $a_i$ dollars to move the element $p_i$.

Your goal is to make it so that each element of the first set is less than each element of the second set. Note that if one of the sets is empty, this condition is met.

For example, if p=[3,1,2] and a=[7,1,4], then the optimal strategy is: separate p into two parts [3,1] and [2] and then move the 2-element into first set （it costs 4）. And if p=[3,5,1,6,2,4], a=[9,1,9,9,1,9], then the optimal strategy is: separate p into two parts [3,5,1] and [6,2,4], and then move the 2-element into first set （it costs 1）, and 5-element into second set （it also costs 1）.

Calculate the minimum number of dollars you have to spend.

输入描述

The first line contains one integer n $(2≤n≤2⋅10^5)$ — the length of permutation.

The second line contains n integers $p_1,p_2,…,p_n$ $(1≤p_i≤n)$. It’s guaranteed that this sequence contains each element from 1 to n exactly once.

The third line contains n integers $a_1,a_2,…,a_n (1≤a_i≤10^9)$.

输出描述

Print one integer — the minimum number of dollars you have to spend.

思路分析

一开始给你一个序列，每个位置都有一个移动他的代价$a_i$，最开始你可以分成两个不空的集合，然后移动过后，使第一个集合中的元素全部小于第二个集合，或者有一个为空集。
思路：

• 枚举第一个集合剩余$i$个元素，那么它的元素肯定是$[1,i]$所有的，除了空集。
• 有一个基础贡献$base$,要满足，假设要移动$[1,i]$所有，那么这个贡献就是这些之和。
• 将$[1,i]$的位置上的贡献取负数，那么在前缀里面，如果它的位置已经满足了，那么就会抵消掉$base$中的贡献。
• 需要注意的是不能一开始有空集，所以是$[1,n-1]$的前缀，且$ans$一开始应该为a[1]（也就是把第一个集合移空的操作的最少花费）

所以，我们可以用一个线段树来维护前缀最小值。

样例输入

3
3 1 2
7 1 4

样例输出

4

AC代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define int long long
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=2e5+10;

struct Btree {
    int left,right,lmi,sum;
} tree[N<<2];

int p[N],a[N],pos[N];

void pushup(int x) {
    if(tree[x].left==tree[x].right)
        return ;
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
    tree[x].lmi=min(tree[x*2].lmi,tree[x*2].sum+tree[x*2+1].lmi);
}

void build(int x,int l,int r) {
    tree[x].left=l;
    tree[x].right=r;
    if(l==r) {
        tree[x].lmi=tree[x].sum=a[l];
        return ;
    } else {
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
    }
    pushup(x);
}

void update(int x,int p,int v) {
    if(tree[x].left==tree[x].right) {
        tree[x].lmi=v;
        tree[x].sum=v;
    } else {
        int mid=(tree[x].left+tree[x].right)/2;
        if(p<=mid)
            update(x*2,p,v);
        else
            update(x*2+1,p,v);
        pushup(x);
    }
}

pair<int,int> query(int x,int l,int r) {
    if(l<=tree[x].left && tree[x].right<=r) {
        return mp(tree[x].sum,tree[x].lmi);
    } else {
        int mid=(tree[x].left+tree[x].right)/2;
        if(r<=mid)
            return query(x*2,l,r);
        if(l>=mid+1)
            return query(x*2+1,l,r);
        pair<int,int>ls=query(x*2,l,r);
        pair<int,int>rs=query(x*2+1,l,r);
        return mp(ls.fi+rs.se,min(ls.se,ls.fi+rs.se));
    }
}

signed main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int n;
    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=1;i<=n;i++)
        pos[p[i]]=i;
    build(1,1,n);
    int base=0;
    int ans=a[1];
    for(int i=1;i<=n;i++){
        base+=a[pos[i]];
        update(1,pos[i],-a[pos[i]]);
        ans=min(ans,query(1,1,n-1).se+base);
    }
    
    cout<<ans<<endl;
    



    return 0;
}