题解 P6186 【[NOI Online 提高组]冒泡排序(民间数据)】
xht
2020-03-07 21:42:17
考虑冒泡排序一轮对逆序对的变化。
首先给出结论:假设原本在位置 $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;
}
```