题解 P6186 【[NOI Online 提高组]冒泡排序(民间数据)】

xht

2020-03-07 21:42:17

Solution

考虑冒泡排序一轮对逆序对的变化。 首先给出结论:假设原本在位置 $i$ 上的逆序对数为 $c_i$,冒泡排序一轮后,位置 $i$ 上的逆序对数变为 $\max(0, c_{i+1}-1)$。 相当于一个**左移,减一,与 $0$ 取 $\max$** 的过程。 为什么呢? 冒泡排序一轮的本质,其实就是从第一个数开始,将其拿出来,放到它后面第一个比它大的数之前,然后将比它大的那个数拿出来,再往后放,以此类推。 假设我们拿出来的数原本的下标为 $i$,要放到下标为 $j$ 之前的位置,则 $(i,j)$ 这个里面的数全部往前移了一位,同时在它们上面的逆序对数少了一个。 而拿出来的数一定是逆序对数为 $0$ 的位置,否则前面一定有比它大的数,它就一定不会被拿出来。 因此**左移,减一,与 $0$ 取 $\max$** 的过程就是逆序对数变化的过程。 有了这个结论,剩下的就好做了,用树状数组维护每个逆序对数的个数以及它们对答案的贡献即可。 ```cpp const int N = 2e5 + 7; int n, m, a[N], b[N], c[N]; ll s[N]; inline void add(int x, int k, ll w = 0) { while (x <= n) c[x] += k, s[x] += w, x += x & -x; } inline pair<int, ll> ask(int x) { int k = 0; ll w = 0; while (x) k += c[x], w += s[x], x -= x & -x; return mp(k, w); } int main() { rd(n), rd(m), rda(a, n); for (int i = 1; i <= n; i++) b[i] = ask(n).fi - ask(a[i]).fi, add(a[i], 1); for (int i = 1; i <= n; i++) c[i] = 0; for (int i = 1; i <= n; i++) if (b[i]) add(b[i], 1, b[i]); while (m--) { int o, x; rd(o), rd(x); if (o == 1) { if (a[x] < a[x+1]) { if (b[x]) add(b[x], -1, -b[x]); ++b[x]; if (b[x]) add(b[x], 1, b[x]); } else { if (b[x+1]) add(b[x+1], -1, -b[x+1]); --b[x+1]; if (b[x+1]) add(b[x+1], 1, b[x+1]); } swap(a[x], a[x+1]), swap(b[x], b[x+1]); } else { if (x >= n) print(0); else { pair<int, ll> p1 = ask(n), p2 = ask(x); print(p1.se - p2.se - 1ll * (p1.fi - p2.fi) * x); } } } return 0; } ```