# 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`

## 代码

```#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;
}```

0 条评论

• ### F2. Animal Observation (hard version)

time limit per test：3 seconds memory limit per test：512 megabytes inputstandard ...

• ### 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

• ### D. Minimax Problem

time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

• ### POJ-2181 Jumping Cows（贪心）

Jumping Cows Time Limit: 1000MS Memory Limit: 65536K Total Submissions:...

• ### visualize your CDS view via Analysis Path Framework (APF)

Create a new configuration which acts as a container for sub settings such as Fi...

• ### WPF框架的内存泄漏BUG

用户在使用GIX4某模块的过程中，内存只见加不见减。我们怀疑出现了内存泄漏，所以我花了相当一段时间来进行此问题的排查。     我使用Red Gate公...

• ### SAP UI5应用的调试标志位的本地存储逻辑 - local storage使用的一个例子

We know that once we enable debug mode via “Ctrl+Alt+Shift+P”, this setting will...

• ### 多语种机器翻译: 缩小共享和特定语言编码解码器之间的差距（CS CL)

最先进的多语种机器翻译依赖于通用的编码解码器，这需要重新训练整个系统来添加新的语言。 在本文中，我们提出了一种基于特定语言编码解码器的替代方法，从而可以更容易地...

• ### 【2019年8月版本】OCP 071认证考试最新版本的考试原题-第2题

Which three are true about the CREATE TABLE command?

• ### APF model和Fiori launchpad tile的同步问题

If I create a new representation in APF modeler: