[NOI Online 提高组]冒泡排序

本文主要是介绍[NOI Online 提高组]冒泡排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

冒泡排序

题解

~~反正我考场上是错的就对了。~~

本题是要求逆序对数量，经过k次排序的逆序对数。于是很容易联想到这道冒泡排序。

由于时间复杂度的限制，我们的暴力明显只能拿20pts，毕竟是 $O\left(n^{2} \right )$ 的。

换言之，我们必须知道每一轮冒泡排序对逆序对整体数量的影响，~~从联想的题目~~ 枚举推测可得，是左边有比它本身值大的数的个数。因为对于一个数在一轮冒泡排序中，如果它的左边有数比它本身大，那在本轮排序中它肯定会与它左边最大的数交换，于是会减少一个逆序对。

很明显，如果我们用 $O\left(n \right )$ 的方法去执行冒泡排序，它还是会T。于是我们还需要引入像树状数组这样的数据结构去维护。用差分加树状数组，就可以 $O\left(logn \right )$ 的去处理了。

对于每次交换的操作，只有可能产生1个逆序对的影响，我们只需要对树状数组进行修改即可，还是 $O\left(logn \right )$ 。

源码

~~我也不知道为什么考场上打的线段树会WA，而下来打的树状数组没事，ZiBi++。~~

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<time.h>
using namespace std;
#define MAXN 200005
typedef long long LL;
#define int LL
#define lowbit(i) (i&-i)
typedef pair<int,int> pii;
#define gc() getchar()
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
int n,m,tot,a[MAXN],b[MAXN],c[MAXN],tree[MAXN];
void insert(int x,int w){while(x<=n)tree[x]+=w,x+=lowbit(x);
}
int query(int x){int res=0;while(x>0)res+=tree[x],x-=lowbit(x);return res;
}
signed main(){read(n);read(m);for(int i=1;i<=n;i++){read(a[i]);b[i]=i-1-query(a[i]);tot+=b[i];c[b[i]]++;insert(a[i],1);}memset(tree,0,sizeof(tree));insert(1,tot);tot=0;for(int i=1;i<=n;i++)tot+=c[i-1],insert(i+1,tot-n);for(int i=1;i<=m;i++){int opt,x;read(opt);read(x);x=min(x,n-1);if(opt==2)printf("%lld\n",query(x+1));else if(a[x]<a[x+1]){swap(a[x],a[x+1]);swap(b[x],b[x+1]);b[x+1]++;insert(b[x+1]+1,-1);insert(1,1);}else{swap(a[x],a[x+1]);swap(b[x],b[x+1]);insert(b[x]+1,1);b[x]--;insert(1,-1);}}return 0;
}