题解：CF2003E2 Turtle and Inversions (Hard Version)

· · 题解

区间不相交怎么做？先来一大波观察。

对不在区间的数，一定是和前缀序列接上，或者和后缀序列接上，且对于一段连续不在区间的数不可能一些接前缀一些接后缀。 结合数据范围考虑 dp，设 $f_{i,j}$ 为前 $i$ 个区间，包括在区间与不在区间的数前缀序列当前长度为 $j$ 的最小**顺序对**数。 - 对区间，转移枚举当前区间前缀放 $k$ 个，后缀会和之前区间的前缀产生贡献。 - 对不在区间的数，有接上前缀序列和后缀序列两种转移。 区间总长度是 $O(n)$ 的，故复杂度 $O(n^2)$，通过 E1。 现在区间会相交。每个区间都要划分出前缀和后缀，但如果一个数既在前缀又在后缀一定不合法。所以对区间取并，每个大区间中的所有区间断点要相同，如果这些区间无交或者交集为 $1$ 就无解。否则变成强制断点处于这些区间的交，做一遍 dp。 [代码。](https://codeforces.com/contest/2003/submission/383551936)