Easy Fix (排序+树状数组+离线处理+找规律)

题目:

给定长度为 n 的排列 p，令 Ai 表示 i 左边比 pi 小的数字个 数，Bi 表示 i 右边比 pi 小的数字个数，Ci = min(Ai , Bi)。 有 m 次独立的询问，每次询问给定 u 和 v，问如果交换 pu 和 pv， ∑n i=1 Ci 的值将会是多少。 n ≤ 100000。 m ≤ 200000

Problem - F - Codeforces

思路:

• 首先是可以进行排序+树状数组来把 A,B求出来
• 然后是对询问的处理, 离线处理
• 对于本身 Cl, Cr 就是 离线 预处理弄的时候就搞出来
• 然后对于 L,R, 内的数怎么办呢?
• 暴力做一定是超时的
• 就找规律
• 发现他一定是 l <X <r 或者 R>X>L 才会对答案进行更新
• 然后对贡献加减, 分别考虑, 即可发现规律
• 继续 离线的预处理就OK了