主观难度：【2】
其实我当时的想法已经非常接近了。但是也只是非常接近了。
前面忘了。
注意到在每一轮冒泡排序后，对于每个不是前缀最大值的数都会有一个数被移到后面去，亦即以该点为较后点的逆序对数量减一。
设以点 \(i\) 为较后点的逆序对数量为 \(b_i\)，则有 \(\mathrm{answer} = \sum_{i = 1}^{n} \max \{ b_i-k, 0 \}\)。
用你喜欢的方式维护这个东西即可。我比较喜欢权值树状数组。
#include <bits/stdc++.h>
#define llong long long
#define N 200005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, q;
int a[N]; llong b[N];int tmp[N];
llong fwk1[N], fwk2[N];
#define lowbit(x) (x&-x)
template<typename T>
inline void modify(T fwk[], int x, T k){for(int i = x+1; i <= n+1; i += lowbit(i)) fwk[i] += k;}
template<typename T>
inline T query(T fwk[], int x){T res = 0; for(int i = x+1; i; i ^= lowbit(i)) res += fwk[i]; return res;}int main(){read(n, q);for(int i = 1; i <= n; ++i) read(a[i]);for(int i = 1; i <= n; ++i){b[i] = (i-1)-query(tmp, a[i]);modify(fwk1, b[i], 1ll), modify(fwk2, b[i], b[i]);modify(tmp, a[i], 1);}while(q--){int op, x; read(op, x);if(op == 1){modify(fwk1, b[x], -1ll), modify(fwk2, b[x], -b[x] );modify(fwk1, b[x+1], -1ll), modify(fwk2, b[x+1], -b[x+1]);if(a[x] < a[x+1]) ++b[x];else --b[x+1];swap(a[x], a[x+1]), swap(b[x], b[x+1]);modify(fwk1, b[x], 1ll), modify(fwk2, b[x], b[x] );modify(fwk1, b[x+1], 1ll), modify(fwk2, b[x+1], b[x+1]);}if(op == 2){x = min(x, n);printf("%lld\n", query(fwk2, n)-query(fwk2, x)-(n-query(fwk1, x))*x);}}return 0;
}