洛谷P6186 [NOI Online #1 提高组] 冒泡排序 题解

题目链接：P6186 [NOI Online #1 提高组] 冒泡排序

题意：支持交换 $a_x$ 和 $a_{x+1}$ 和查询 $k$ 轮冒泡排序后的逆序对个数， $a$ 数组是长度为 $n$ 的排列

首先逆序对这个东西可以用树状数组搞定

题目给的是排列，因此求逆序对的伪代码如下

for i=1~n:
    f[i]=i-sum(a[i])-1,add(a[i],1)

当然如果不是排列会稍微烦一点，可以看下我的这篇文章

设 $f[i]$ 表示在 $i$ 左侧比 $i$ 大的数的个数，那么逆序对就是 $\sum\limits_{i=1}^{n}{f[i]}$

（注：这里的 $f[i]$ 就是上面伪代码中的 qwq）

我们看看冒泡排序了 $k$ 次以后会发生什么事

首先每次冒泡排序所有的 $f[i]$ 都会减少 $1$ 当且仅当 $f[i]>0$

那么 $k$ 次之后所有小于等于 $k$ 的 $f[i]$ 都会变成 $0$

因此我们只要每次就查询 $[k+1,n]$ 中 $f[i]$ 的个数就是答案了

这个我们可以用两个树状数组来维护答案

再看看这个交换操作，可能会影响到其他的答案

那么怎么办呢？根据刚才我们发现的性质，我们可以先把它们两个的贡献减掉 $1$ ，然后按 $a_x$ 和 $a_{x+1}$ 的大小关系分别处理答案的变化，再把原先的贡献补回来就好了

代码实现有点烦，主要是有点乱

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(2e5+5)
template<typename T>inline void read(T &k)
{
	char ch=getchar();T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	k=x*f;
}
template<typename T>inline void write(T k)
{
	if(!k){putchar('0');return;}
	if(k<0){k=-k;putchar('-');}
	if(k>9)write(k/10);
	putchar(k%10+'0');
}
int n,m;
int a[MAXN],f[MAXN];
struct BIT
{
	int bit[MAXN];
	void clear(){memset(bit,0,sizeof(bit));}
	inline int lowbit(int x){return x&(-x);}
	void add(int x,int v)
	{while(x&&x<=n){bit[x]+=v;x+=lowbit(x);}} // 这里是坑点，f[]可能为0
	int sum(int x){int res=0;while(x>=1){res+=bit[x];x-=lowbit(x);}return res;}
	int qry(int l,int r){return sum(r)-sum(l-1);}
}bt[2];
// 两个树状数组维护的东西不一样哦 qwq
void upd(int x,int v){bt[0].add(x,v);bt[1].add(x,v*x);} 
int qry(int l,int r){return bt[1].qry(l,r)-bt[0].qry(l,r)*(l-1);}
inline void Swap(int x)
{
	upd(f[x],-1);
	upd(f[x+1],-1); 
	if(a[x]>a[x+1])--f[x+1]; // 分情况讨论
	else ++f[x];
	swap(a[x],a[x+1]);swap(f[x],f[x+1]);
	upd(f[x],1);
	upd(f[x+1],1);
}
signed main()
{
	read(n);read(m);
	for(int i=1; i<=n; i++)
	{
		read(a[i]);
		f[i]=i-bt[0].sum(a[i])-1;
		bt[0].add(a[i],1);
	} // 先拿一个树状数组临时用一下
	bt[0].clear();
	for(int i=1; i<=n; i++)
		upd(f[i],1);
	while(m--)
	{
		int op,k;
		read(op);read(k);
		if(op==1)Swap(k);
		if(op==2)write(k+1>n?0:qry(k+1,n)),putchar('\n'); // 特判勿忘
	}
	return 0;
}