题解 P6186 【[NOI Online 提高组]冒泡排序（民间数据）】
xukuan
2020-03-14 21:25:46
~~大菜鸡xukuan一开始以为一次冒泡排序只会减少一个逆序对~~
我们令$sum_i$表示第$i$个数字前有$i$个比他大的。
显然每次排序后，$sum_i$都会减少1，但$sum_i$不会小于0
证明
- 如果$sum_i=0$显然$sum_i$还是0
- 如果$sum_i>0$，那么前面肯定会有一个比他大的数字转到后面。所以$sum_i$减少1
那么转了k次后，总逆序对个数就是$\sum_{i=1}^n max(0,a_i)$
我们开两个树状数组，一个维护每个点的逆序对个数，另一个维护大于k的数的和。
至于修改：先删除原来的影响（树状数组的删除，val=-1的修改），再改值，换位，最后加回去。
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=200010;
ll n,m,p[N],nxd[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
struct BITmentTree{
ll sum[N];
inline ll lowbit(ll x){
return x&(-x);
}
inline void update(ll x,ll val=1){
for(ll i=x; i<=n; i+=lowbit(i)) sum[i]+=val;
}
inline ll query(ll x){
ll ans=0;
for(ll i=x; i; i-=lowbit(i)) ans+=sum[i];
return ans;
}
inline ll query(ll l,ll r){
return query(r)-query(l-1);
}
}a,b;
inline void update(ll x,ll val=1){
a.update(x,val);
b.update(x,val*x);
}
inline ll query(ll l,ll r){
return b.query(l,r)-(l-1)*a.query(l,r);
}
int main(){
freopen("bubble.in","r",stdin);
freopen("bubble.out","w",stdout);
n=read(); m=read();
for(ll i=1; i<=n; i++) p[i]=read();
for(ll i=1; i<=n; i++){
nxd[i]=i-a.query(p[i])-1;
a.update(p[i]);
}
memset(a.sum,0,sizeof(a.sum));
for(ll i=1; i<=n; i++){
if(nxd[i]) update(nxd[i]);
}
while(m--){
ll op=read(),x=read();
if(op==2){
if(x>=n){
printf("0\n");
continue;
}
write(query(x+1,n)); putchar('\n');
}
else{
if(nxd[x]) update(nxd[x],-1);
if(nxd[x+1]) update(nxd[x+1],-1);
if(p[x]>p[x+1]) nxd[x+1]--; else nxd[x]++;
swap(nxd[x],nxd[x+1]); swap(p[x],p[x+1]);
if(nxd[x]) update(nxd[x],1);
if(nxd[x+1]) update(nxd[x+1],1);
}
}
fclose(stdin); fclose(stdout);
return 0;
}
```