Codeforces ECR #081 : E. Permutation Separation

せっかく最終問題まで解いたのにBを落とした回。
http://codeforces.com/contest/1295/problem/E

問題

Permutation Pが与えられる。
これをまず任意の位置で前半と後半に分けたとする。
その後一部の要素を前後半の間で移動し、前半の最大要素より後半の最小要素の方が大きくなるようにしたい。
その際、元のPのi番目の要素の移動にかかるコストC[i]が与えられている。

条件を満たすのにかかる最小コストを求めよ。

解法

f(x) := x以上の値を後半に、x未満の値を前半に集めるときのコスト
ととし、最小値をとるデータ構造を作ろう。
これは累積和と最小値を求めるSegTreeがあればよい。

初期状態の区切り位置を総当たりしながら、上記f(x)の値を更新していき、その都度最小値を確認していけばよい。

int N;
int P[202020];
ll A[202020];

static ll const def=(1LL<<60);
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_3<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) {
		cin>>A[i];
		st.update(P[i],N+1,A[i]);
	}
	ll mi=1LL<<60;
	FOR(i,N-1) {
		st.update(P[i],N+1,-A[i]);
		st.update(0,P[i],A[i]);
		mi=min(mi,st.getval(0,N+1));
		
	}
	cout<<mi<<endl;
	
}

まとめ

SegTreeの構築を除くと意外にシンプルな問題。