CodeChef August Lunchtime 2015

官方solution：https://discuss.codechef.com/tags/ltime27/

这场比赛还是挺恶心好玩的

以下纯属口胡。

【MNMX】

显然每次在最小值旁边选一个然后删掉它即可，答案等于$\text{minvalue}\times (n-1)$。

【CLOST】

我的构造方法是这样的：

$\text{for }i = 1\text{ to }k$

    $\text{for }j = l_i\text{ to }r_i$

        $t = \text{'('}$

        $\text{if }(s_j == \text{empty})$

            $s_j = t$

        $t = \text{'('} + \text{')'} - t$

哦之前要把区间排序。。由于答案存在，所以不会有相交但是不包含的区间，所以只要访问一个区间之前，它包含的所有区间都被访问完了即可。

证明嘛。。假设有括号序列$()()()\dots ()$，在其中任何位置插入一个括号序列之后它还是合法的括号序列。

【MAKPALIN】

枚举改变哪一位，然后使用恶心的分类讨论来检验。开始觉得要分奇偶讨论，后来发现式子长得一样。。没必要分类。。就呵呵了。

检验的时候用任何查询LCP神器都可以。(Hash，后缀数组等)

【INVERT】

我在下考前1分钟调出了这题的最后一个bug

考虑问题的简化版，$n$个位置，一些位置是空的，一些位置有数字。每个时候会在一个空位中插一个数字(所以一个位置上顶多一个数字)，每次操作之后求逆序对数。

为了求逆序对数我们需要知道“一个数前面有多少比它大的数”这类询问。线段树套平衡树显然可做。

然后我们用splay模拟出$A$中的数最后去了$B$中的哪儿(没错，我离线了)，然后就可以转化为这个问题～