Educational Codeforces Round 81 (Rated for Div. 2) E. Permutation Separation(线段树)

题目链接：https://codeforces.com/contest/1295/problem/E

 

题目大意：

  有一个序列，是1~n的某一种排序，取一个位置将它分为前缀和后缀，分别形成一个集合。将一个数字移到另一个集合需要$p[i]$p[i]的代价，问使得第一个集合中所有的数字都小于第二个集合中的所有数字(就是第一个集合中最大的数字要小于第二个集合中最小的数字)的最小代价，如果某一集合为空也符合要求。

 

题目思路：

  $n^2$n2做法显而易见：首先由于左边的最大数字要小于右边的最小数字，所以左边一定是1~i的一个序列，所以枚举这个i，然后里面就枚举分割的位置，然后将左边闲杂数字踢掉，右边需要的数字请回来，然后取最小值。
  作为一个菜鸡，没有想到用线段树来优化这个东西。。实属菜鸡。后来看到线段树三个字后我又想了会儿，好像跟其他题解的做法稍有不同，但是我更喜欢我自己的。线段树每个节点表示，割在这个位置需要的代价，线段树维护最小值。我是这么做的，对于这个区间，我从k到2枚举，这样做的好处是，我就可以理解成从k到2删除点，也就是当前所有还存活的点都是左边集合的点，剩下来的点一定还能满足从1~i，不会出现越级。最开始的时候，1~n全都在，那么对于每个分割点来说，左边没有要赶走的点，而右边的所有的点都是需要来帮忙的。当删除n的时候，对于n和n右边的点来说，他们之前盖住了n，但现在n是当前集合不要的点，所以他们要加上n的代价，也就是把它踢出去，而它们左边的点，之前需要花费代价把它请回来，现在这个点不复存在，所以这个代价可以删掉了。
  由于其中一个是空集也符合要求，所以刚开始先ans取$min(p[1],p[n])$min(p[1],p[n])(我用p数组存代价)，还有个坑点是，线段树i节点表示将1~i分割为前缀的情况，所以n是不能取到的。。就因为这我自闭半天。。讲道理，这题实际难度并不算特别高，代码实现也比较简单，还是感觉用线段树维护这个点有点难想到，但是想到后又感觉好像很顺理成章，还是水平问题。

 

以下是代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN=2e5+5;
const int MOD=1e9+7;
ll p[MAXN],b[MAXN],pos[MAXN],sum[MAXN];
struct node{
    int l,r;
    ll val,mark;
}a[MAXN<<2];
void build(int rt,int l,int r){
    a[rt].l=l,a[rt].r=r,a[rt].mark=0;
    if(l==r){
        a[rt].val=sum[l+1];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    a[rt].val=min(a[rt<<1].val,a[rt<<1|1].val);
}
void spread(int rt){
    if(a[rt].mark){
        a[rt<<1].val+=a[rt].mark;
        a[rt<<1|1].val+=a[rt].mark;
        a[rt<<1].mark+=a[rt].mark;
        a[rt<<1|1].mark+=a[rt].mark;
        a[rt].mark=0;
    }
}
void update(int rt,int l,int r,ll val){
    if(l>r)return;
    if(a[rt].l>=l&&a[rt].r<=r){
        a[rt].val+=val;
        a[rt].mark+=val;
        return;
    }
    spread(rt);
    int mid=(a[rt].l+a[rt].r)>>1;
    if(l<=mid)update(rt<<1,l,r,val);
    if(r>mid)update(rt<<1|1,l,r,val);
    a[rt].val=min(a[rt<<1].val,a[rt<<1|1].val);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin>>n){
        rep(i,1,n)cin>>b[i],pos[b[i]]=i;
        rep(i,1,n)cin>>p[i];
        sum[n+1]=0;
        per(i,n,1){
            sum[i]=sum[i+1]+p[i];
        }
        ll ans=min(p[1],p[n]);
        build(1,1,n-1);
        per(i,n,2){
            update(1,1,pos[i]-1,-p[pos[i]]);
            update(1,pos[i],n-1,p[pos[i]]);
            ans=min(ans,a[1].val);
        }
        cout<<ans<<endl;
    }
    return 0;
}