sol:
考虑一下冒泡排序的过程,从左侧开始,将第一个数\(x_1\)拿到第一个比它的的位置,同时将这个比它大的数\(x_2\)拿到下一个比x_2的的位置,这样一直循环下去。
假设有一次操作,我们将x[i]拿到比它大的位置j上去,那么(i, j)这个区间中的数相当于往前移动的一位,并且逆序对数会减少1。并且我们发现,x[i]的逆序对数一定是0,因为如果不是0,
那么它就不可能被拿出来。 那么我们可以得到一个结论,经过一轮冒泡排序,第i个位置上的数的逆序对数变为 :
经过k轮冒泡排序,那么答案为:
\[ans = \sum_{i >=k + 1} (c_i - k) \]可以用两个权值树状数组来维护。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 100;
typedef long long LL;
LL tr[N], T[N], c[N], ans;
int n, q, a[N];
inline int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for(; x <= n + 3; x += lowbit(x))
tr[x] += v;
}
LL ask(int x) {
LL res = 0;
for(; x; x -= lowbit(x))
res += tr[x];
return res;
}
void change(int x, int v) {
for(; x <= n + 3; x += lowbit(x))
T[x] += v;
}
LL query(int x) {
LL res = 0;
for(; x; x -= lowbit(x))
res += T[x];
return res;
}
void output(LL* s) {
puts("Debug");
for(int i = 1; i <= n; i ++)
printf("%lld ", s[i]);
puts("");
}
int main()
{
//#ifdef LOCAL
// freopen("E:\\data.in.txt", "r", stdin);
//#endif
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
c[i] = ask(n) - ask(a[i]);
add(a[i], 1);
if( c[i]) change(c[i], c[i]);
}
for(int i = 1; i <= n; i ++) add(i, -1);
for(int i = 1; i <= n; i ++)
if(c[i]) add(c[i], 1);//下标不能为0
while(q --) {
int op, x;
scanf("%d%d", &op, &x);
if( op == 1) {
if(c[x])
change(c[x], -c[x]), add(c[x], -1);
if(c[x + 1])
change(c[x + 1], -c[x + 1]), add(c[x + 1], -1);
swap(c[x], c[x + 1]);
if( a[x] < a[x + 1]) {
c[x + 1] ++;
change(c[x + 1], c[x + 1]);
add(c[x + 1], 1);
if(c[x])
change(c[x], c[x]), add(c[x], 1);
} else {
c[x] --;
if(c[x])
change(c[x], c[x]), add(c[x], 1);
if(c[x + 1])
change(c[x + 1], c[x + 1]), add(c[x + 1], 1);
}
swap(a[x], a[x + 1]);
} else {
if(x >= n) {
puts("0");
continue;
}
ans = query(n + 1) - query(x);
ans -= x * (ask(n + 1) - ask(x));
printf("%lld\n", ans);
}
}
return 0;
}
/*
3 6
2 1 3
2 0
*/