资讯详情

8.16~8.31

CF2003E1

发现区间前半部分的数和区间右面的数可以分成小于等于和大于某个数的两种，我们枚举这个数，设小于等于这个数的数为 \(A\)，大于这个数的为 \(B\)，然后进行 DP，设 \(f_{i,j}\) 表示考虑前 \(i\) 个数，形如 \(BA\) 状物逆序对数量（因为 \(AA\) 和 \(BB\) 状物最后统计答案能直接算），然后我们发现不用枚举这个数了，因为 \(j\) 就是这个数，接着我们发现区间里如果有 \(ABAB\) 这种不合法状物的话，我们不用管，因为这种一定不会优于合法答案（比如 \(ABBB\)）。

滚动数组每次枚举的时候都要清空