E. Permutation Separation

E. Permutation Separation

E. Permutation Separation time limit per test：2 seconds memory limit per test：256 megabytes inputstandard input outputstandard output

 You are given a permutation p1,p2,…,pn (an array where each integer from 1 to n appears exactly once). The weight of the i-th element of this permutation is ai.  At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements p1,p2,…,pk, the second — pk+1,pk+2,…,pn, 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 ai dollars to move the element pi.  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.

Input The first line contains one integer n (2≤n≤2⋅10^5^) — the length of permutation. The second line contains n integers p1,p2,…,pn (1≤pi≤n). It’s guaranteed that this sequence contains each element from 1 to n exactly once. The third line contains n integers a1,a2,…,an (1≤ai≤10^9^). Output Print one integer — the minimum number of dollars you have to spend.

Examples input

3
3 1 2
7 1 4

output

4

input

4
2 4 1 3
5 9 8 3

output

3

input

6
3 5 1 6 2 4
9 1 9 9 1 9

output

2

题目大意

给你一个数 n ，然后有n个数，给个数对应一个权值ai，然后让你将这n个数分成两个空的几何，通过移动两个几何中的元素，使得最终的左侧几何的数全部小于右侧几何的数，有个特殊情况： 如果移动到最后一个几何为空，那么也成立。移动每一个元素时都要加上对应的权值，问你是如何移动使得花费最小。 比如说第一个样例 3 1 2 这三个数分别对应的权值是 7 1 4，我们可以选择将几何这个序列分成两部分，【3，1】，【2】，这样的话，将2移动到前那个几何中就可以花费为 4且代价最少。

解题思路

这题我们可以考虑把前K个数里面的比K大的数都移动到K后面，K后面比K小的数都移动到K前面，但是如果直接这样写是N^2^的复杂度，这时候我们就要想想可以用什么来优化下了，我们可以模拟先来一遍 就第一个样例吧，刚开始是 3 5 1 6 2 4，对应的权值为9 1 9 9 1 9；假设这时候我们考虑把前k个数全部移动到后面的花费 分别是 9 10 19 28 29 9（对于最后一个数，我们可以考虑，把他向前一个移动） 这是我们发现其实对于前K个数而言，只要其小于等于K，就不用移动，对于K后面的数如果大于K就不用移动，这时候我们该如何优化呢，如果数字 i 的位置在 i 之前，那么 i 位置后面的前缀和要减去 i 的权值，但是要向前去移动，再算前缀和的时候，它前面的数值没有加上他，所以从数字 i 的 位置之前的前缀和都要加上 i 的权值，从 i 的位置开始以后的前缀和都要减去 i 的权值；这样我们就可以线性的跑一遍数列并且以 log 级别的进行计算。 例如： 的后 【3 5 1 6 2 4】 k=1时： 1前面的数字都要加上1的权值，后面的减去1的权值。 k=2时： 2前面的数字都要加上2的权值，后面的减去2的权值。这时候可以发现，2这个位置的前缀和刚好只有3 5 6，这几个数值的权值和， k=3时： 3前面的数字都要加上3的权值，后面的减去3的权值，这时候3这个位置的前缀和变成了 1，2这两个数值的前缀和，并且1这个位置的前缀和变成了2 和5 的权值和了。 后面的也类似就不一一举例了。 线段树本菜鸡也是刚刚学，还请大佬们多多指导。。。

代码

#include<bits/stdc++.h>
using namespace std;
const int mx=200015;
#define ll long long
ll sum[mx];
int a[mx],pos[mx],b[mx];
struct node{
    ll mi,lazy;
} tree[mx<<2];
int n;

inline void build(int x,int l,int r)
{
    if(l==r) {
        tree[x].mi=sum[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    tree[x].mi=min(tree[x<<1].mi,tree[x<<1|1].mi);
    return ;
}

inline void push_down(int x,int l,int r)
{
    tree[x<<1].lazy+=tree[x].lazy;
    tree[x<<1].mi+=tree[x].lazy;
    tree[x<<1|1].lazy+=tree[x].lazy;
    tree[x<<1|1].mi+=tree[x].lazy;
    tree[x].lazy=0;
}

inline void update(int x,int l,int r,int ql,int qr,ll k)
{
    if(r<ql||l>qr) return;
    if(l>=ql&&r<=qr){
        tree[x].lazy+=k;
        tree[x].mi+=k;
        return ;
    }
    push_down(x,l,r);
    int mid=(l+r)>>1;
    update(x<<1,l,mid,ql,qr,k);
    update(x<<1|1,mid+1,r,ql,qr,k);
    tree[x].mi=min(tree[x<<1].mi,tree[x<<1|1].mi);
    return ;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pos[a[i]]=i;//记录a[i]的位置
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        sum[i]=sum[i-1]+b[i];//计算前缀和
    }
    build(1,1,n-1);//建树建到 n-1；
    ll ans=tree[1].mi;//考虑将最后一个数移动到前面花费最小；
    for(int i=1;i<=n;i++)
    {
        update(1,1,n-1,1,pos[i]-1,b[pos[i]]);//这个位置之前的数都要加上i的权值
        update(1,1,n-1,pos[i],n-1,-b[pos[i]]);//这个位置开始以后的数值都要减去i的权值
        ans=min(ans,tree[1].mi);//每次更新最小的情况
    }
    cout<<ans<<'\n';
    return 0;
}