[Educational Codeforces Round 81 (Rated for Div. 2)]E. Permutation Separation（线段树，思维，前缀和）

E. Permutation Separation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation p1,p2,…,pnp1,p2,…,pn (an array where each integer from 11 to nn appears exactly once). The weight of the ii-th element of this permutation is aiai.

At first, you separate your permutation into two non-empty sets — prefix and suffix. More formally, the first set contains elements p1,p2,…,pkp1,p2,…,pk, the second — pk+1,pk+2,…,pnpk+1,pk+2,…,pn, where 1≤k<n1≤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 aiai dollars to move the element pipi.

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]p=[3,1,2] and a=[7,1,4]a=[7,1,4], then the optimal strategy is: separate pp into two parts [3,1][3,1] and [2][2] and then move the 22-element into first set (it costs 44). And if p=[3,5,1,6,2,4]p=[3,5,1,6,2,4], a=[9,1,9,9,1,9]a=[9,1,9,9,1,9], then the optimal strategy is: separate pp into two parts [3,5,1][3,5,1] and [6,2,4][6,2,4], and then move the 22-element into first set (it costs 11), and 55-element into second set (it also costs 11).

Calculate the minimum number of dollars you have to spend.

Input

The first line contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the length of permutation.

The second line contains nn integers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). It's guaranteed that this sequence contains each element from 11 to nn exactly once.

The third line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

Output

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

Examples

input

Copy

output

Copy

input

Copy

output

Copy

input

Copy

6

3 5 1 6 2 4

9 1 9 9 1 9

output

Copy

题意：

给定一个整数n以及一个1~n的全排列，和一个数组a[i]

让你找一个位置划开，将排列分成2个非空的部分，

然后将p[i] 移动到另一个部分的成本是a[i]，

问使左边的所有数都比右边的所有的数小需要的最小成本是多少？

思路：

在区间\([1,n-1]\)枚举切割位置i (从p[i] 右边切开，不取n是因为要保证2部分初始非空) ，时间复杂度\(O(n)\)

那么我们知道所有p[i] 位置后面的小于等于 i 的数都要移动到左边，p[i] 位置即前面的大于 i 的数都要移动到右边。

我们尚若可以\(O(logn)\) 时间内得到上面移动操作的cost就可以维护出最小值。

我们想到了线段树。

首先对a[i] 做一个前缀和数组 sum[i] ，代表将1~i的数都移动到右边需要的cost。

以sum[i] 数组建立区间修改，区间查询最小值的线段树。

然后从1到n-1枚举割切位置i，

对于第i个位置，我们将找到i在p中的位置 id ,将区间\([1,id-1]\) 减去 a[id]，区间\([id,n-1]\) 加上a[id]

意义为：在切割位置大于等于i 的时候，不需要将数字i移动到右边部分，又结合线段树维护的是前缀和数组，

那么对于每一个位置i 用线段树的根节点维护的最小值去更新答案ans即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

#define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))

#define du2(a,b) scanf("%d %d",&(a),&(b))

#define du1(a) scanf("%d",&(a));

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) { if (a == 0ll) {return 0ll;} a %= MOD; ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;}

void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}

inline long long readll() {long long tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}

inline int readint() {int tmp = 0, fh = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') fh = -1; c = getchar();} while (c >= '0' && c <= '9') tmp = tmp * 10 + c - 48, c = getchar(); return tmp * fh;}

const int maxn = 300010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int n;

int p[maxn];

int id[maxn];

ll a[maxn];

ll sum[maxn];

struct node

{

    int l, r;

    ll laze;

    ll val;

} segment_tree[maxn << 2];

void pushup(int rt)

{

    segment_tree[rt].val = min(segment_tree[rt << 1].val, segment_tree[rt << 1 | 1].val);

}

void build(int rt, int l, int r)

{

    segment_tree[rt].l = l;

    segment_tree[rt].r = r;

    if (l == r)

    {

        segment_tree[rt].val = sum[l];

        segment_tree[rt].laze = 0ll;

        return ;

    }

    int mid = (l + r) >> 1;

    build(rt << 1, l, mid);

    build(rt << 1 | 1, mid + 1, r);

    pushup(rt);

}

void pushdown(int rt)

{

    segment_tree[rt << 1 | 1].val += segment_tree[rt].laze;

    segment_tree[rt << 1 | 1].laze += segment_tree[rt].laze;

    segment_tree[rt << 1 ].val += segment_tree[rt].laze;

    segment_tree[rt << 1 ].laze += segment_tree[rt].laze;

    segment_tree[rt].laze = 0;

}

void update(int rt, int l, int r, int num)

{

    if (segment_tree[rt].laze && l != r)

    {

        pushdown(rt);

    }

    if (segment_tree[rt].l >= l && segment_tree[rt].r <= r)

    {

        segment_tree[rt].val += num;

        segment_tree[rt].laze += num;

        return ;

    }

    int mid = segment_tree[rt].l + segment_tree[rt].r >> 1;

    if (r > mid)

    {

        update(rt << 1 | 1, l, r, num);

    }

    if (l <= mid)

    {

        update(rt << 1, l, r, num);

    }

    pushup(rt);

}

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    n = readint();

    repd(i, 1, n)

    {

        p[i] = readint();

        id[p[i]] = i;

    }

    repd(i, 1, n)

    {

        a[i] = readll();

    }

    repd(i, 1, n)

    {

        sum[i] = sum[i - 1] + a[i];

    }

    ll ans = a[n];

    build(1, 1, n - 1);

    ans = min(ans, segment_tree[1].val);

    int x;

    repd(i, 1, n)

    {

        x = id[i];

        if (x != n)

        {

            update(1, x, n - 1, -a[x]);

        }

        if (x != 1)

        {

            update(1, 1, x - 1, a[x]);

        }

        ans = min(ans, segment_tree[1].val);

    }

    printf("%lld\n", ans );

    return 0;

}

巴特西

[Educational Codeforces Round 81 (Rated for Div. 2)]E. Permutation Separation（线段树，思维，前缀和）

[Educational Codeforces Round 81 (Rated for Div. 2)]E. Permutation Separation（线段树，思维，前缀和）

题意：

思路：

代码：

最新文章

热门文章