题解：AT_abc431_g [ABC431G] One Time Swap 2

· · 题解

前情提要

不喜欢语言学的信息学奥赛生小 W 在今晚的 ABC 中扔掉 EF 猛攻 G 题最后得到了高达 1351 的 perf。在这次经历后小 W 和不喜欢字符串一样不喜欢平衡树。

解题思路

我们考虑交换这一操作的性质，可以将 f(l,r) 分三类：

所以我们可以把所有询问离线下来并排序，一边统计一边求答案。具体地：我们维护当前类别的某个 l 有多少个 r 符合要求，同时为在这一范围内的询问分配对应排名的 r。这个过程可以被转化为：插入或删除一个数、求一个数的排名、求排名为 x 的数。用一个平衡树维护即可。

要注意的是本体要输出的是具体的位置而非交换的数值，我们可以在插入数的时候将这个数乘上一个大数再加上它的位置，这样就可以按照数值第一关键字地址第二关键字排序了！改变正负号就可以选择升序降序。