3759专题

Luogu 3759 [TJOI2017]不勤劳的图书管理员

再也不作死写FhqTreap作内层树了,卡的不如暴力呜呜呜……  题意翻译:给一个序列,每个下标包含两个属性$a$和$v$,求第一个属性与下标形成的所有逆序对的第二个属性和,给出$m$个交换两个下标的操作,每次操作之后查询。 考虑一下交换之后会发生什么: 假设这次要交换$x$和$y$,使$x \leq y$。 发现交换之后$x, y$和$x$的左边的数和$y$右边的数构成的逆序对产生的贡献不变