Permutation Separation（线段树）

题目链接：http://codeforces.com/contest/1295/problem/E 题意：给定一个排列，以及每个位置的价值a[]。现在把当前排列分成前后两部分，可以将左边集合的数扔到右边集合，但需要消费该数对应的代价；同理可以将右边集合的数扔到左边集合，但需要消费该数对应的代价。通过若干次移动操作，实现左边集合数恒小于右边集合数。求最小花费。 题解：最终实现左边集合数恒小于右边集合数，等价于左边数 < v a l =val >=val，对于当前选定的 v a l val val，我们判断每个划分位置 p o s pos pos，我们将 < = p o s pos >pos的数放在右集合。那么对于 > p o s , < v a l >pos,pos, = v a l =val =val的数需要从左集合扔到右集合。 用数组 m n [ ] mn[] mn[]来表示对于当前 v a l val val，下标划定为 p o s pos pos需要的最小代价 m n [ p o s ] mn[pos] mn[pos]，从0到n枚举 v a l val val，每次增加1，重点考究每次增加1时 m n [ ] mn[] mn[]的更新，可以发现，当 v a l val val增加为 v a l + 1 val+1 val+1后，原本 > = p o s i t i o n [ v a l ] >=position[val] >=position[val]的位置 m n [ ] mn[] mn[]都减少代价 a [ p o s i t i o n ] a[position] a[position]， < p o s i t i o n [ v a l ]