1x1
F
By Margarita
第一次遇到这种题吗？应该吧，反正印象里没有做到过，虽然感觉应该是个经典题，jly：“F<<<<A”
考虑怎么处理排序，场上我想了个平衡树+启发式合并的做法，但是这个的复杂度是与合并点数相关的，会被卡，所以我们考虑如何整段合并。线段树合并和分裂可以做到这一点，复杂度感性理解一下，因为每次都排序了，就大概是正确的。然后如何统计答案，我们开一个树状数组记录若干整段的答案，查询时强制让查询的点在某一段的末尾，这样就保证了查询的正确性。
主要就是权值线段树合并与分裂维护排序，考虑整段贡献统计答案。
线段树合并与分裂，没有MLE复杂度就是正确的！
J
By Margarita
这个分块，真的神奇，不知道怎么就把复杂度降下来了。
暴力做的话是\(O(n^3)\)的。
以下块为对操作序列的分块，区间为对原序列的分块。
对操作序列分块一次，设块大小为\(B\)，你发现每个块内，原序列只有\(B\)个区间是有用的，这一块内的操作的贡献只会使区间内翻转，或区间与区间交换，直接暴力维护区间复杂度就变成了\(O(n^2/B+nB^2)\ge O(n^{5/3})\)。其中\(O(n^2/B)\)是块操作结束维护原序列的复杂度，\(O(nB^2)\)是对对每个询问暴力\(O(B^2)\)计算答案的复杂度。
那么显然\(O(n^2/B)\)不太能降，考虑怎么降\(O(nB^2)\)。对每个块分治，我们发现分治下去的时候，小块的区间数是在变少的，而且是大块区间的合并，就是比如大块区间有\([1,2],[3,6]\)，那么小块可能就把这两个区间合并为\([1,6]\)，证明显然。我们考虑用这个来进行分治，假设我们已经知道了大块中\(f_{i,j}\)表示在\(i\)区间和\(j\)区间中有几对相同的数字，令块长为\(k\)，我们可以用不超过\(O(k^2)\)的代价处理从大块小区间到小块大区间的映射，然后用\(O(k^2)\)的代价暴力枚举区间，从而计算小块中的\(f\)，那么总时间复杂度就是\(T(k)=2T(k/2)+O(k^2)=O(k^2)\)的，对一个区间处理的代价就是\(O(B^2)\)的，有\(O(n/B)\)个区间，复杂度就是\(O(nB)\)，然后就得到了一个总复杂度\(O(n^2/B+nB)\ge O(n^{3/2})\)的算法，可以通过此题。