题目传送门

Permutation Separation

题目大意：

给出一个1~n的排列,每个对应一个代表这个数的价值
将序列划分成一个前缀和一个后缀，然后移动前后缀中的数到另一边，最终使得前缀中的所有数都小于后缀中的任何一个数，移动任意一个的花费是，求最小的花费。

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).
题目中的解释

思路：

赛中想了个假的三分+DP的方法想莽一波，虽然一开始就觉得三分不靠谱，但是还是试了一下。一直wa到结束。赛后看了dalao的代码，恍然大悟。
枚举以为分界，对于放到左边，放到右边，这样原问题就相当于求一个最优的前后缀分割使得移动的花费最小。
仔(kan)细(dalao)思(dai)考(ma)后发现，实际上对于某一种划分而言，在枚举时，对于右边集合而言，他的贡献实际上就是,而对于左边集合正好相反。
所以我们可以用一棵权值线段树维护答案，每个点表示当前划分下以为分割点时的答案。
初始时我们认为将整个序列划分给右半段，那么对于每个都加上，因为以比大的点作为分割点时，都会被向左边集合移动，产生的贡献。
然后枚举划分的点，每次将右边集合最左边的移动到左边集合，这时对于所有大于等于它的不在有贡献，而是对于所有小于他的产生贡献。在所有贡献中取就是答案。

代码：

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <time.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
//#define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 2e5 + 10;
ll p[maxn], a[maxn];
ll val[maxn << 2], lazy[maxn << 2];
void pushup(int root)
{
    val[root] = min(val[root << 1], val[root << 1 | 1]);
}
void pushdown(int root)
{
    if (lazy[root])
    {
        val[root << 1] += lazy[root];
        val[root << 1 | 1] += lazy[root];
        lazy[root << 1] += lazy[root];
        lazy[root << 1 | 1] += lazy[root];
        lazy[root] = 0;
    }
}

void update(int root, int l, int r, int lt, int rt, int v)
{
    if (l == lt && r == rt)
    {
        val[root] += v;
        lazy[root] += v;
        return;
    }
    int mid = l + r >> 1;
    pushdown(root);
    if(rt<=mid)
        update(lson, lt, rt, v);
    else if(lt>mid)
        update(rson, lt, rt, v);
    else
    {
        update(lson, lt, mid, v);
        update(rson, mid + 1, rt, v);
    }
    pushup(root);
}
int main()
{
    int n;
    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(p[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
    }
    for (int i = 1; i <= n; ++i)
    {
        update(1, 0, n, p[i], n, a[i]);
    }
    ll res = INF << 1;
    for (int i = 1; i < n; ++i)
    {
        update(1, 0, n, p[i], n, -a[i]);
        update(1, 0, n, 0, p[i] - 1, a[i]);
        res = min(res, val[1]);
    }
    printf("%lld\n", res);
}