OI-冒泡排序[NOI Online] | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI-冒泡排序[NOI Online]

发表于 分类于 Valine：

我发现找规律越来越难了（考场上找规律方向与正解恰好相反的我）

# 题面

见洛谷 P6186……

# 解析

Tab. 下面记输入的原数组为 num[]

因为逆序对只会被考虑一次（比如 $(i,j)$ 是逆序对，那 $(j,i)$ 也是，但是只考虑其中一个），不妨对于位置 $i$，只考虑它前面的比它大的位置 $j$，设 val[i] 表示位置 $i$ 前面有 val[i] 个大于 num[i] 的数。

那么考虑进行一轮冒泡排序后 val[] 会怎么变化——

实际上，可以把冒泡排序的过程看成下面这样一些移动操作：

png1

首先，被移动的位置肯定 val[i] 是等于 0 的，也就是说它前面的数都比它小。否则，如果前面有比它大的数，那么那个数移动时就会跳过 i（也就是说 i 作为了上图中蓝色部分）。而且非常显然的是，因为 num[] 是一个 1 到 n 的排列，那么如果 val[i]==0，那么 i 一定会被移动。

另外，我们知道冒泡排序后，val[] 只会变小——除非 val[i]==0。

那么考虑 val[i]>0 的情况，对应的就是上图蓝色部分。我们发现，一次冒泡排序后，恰好有一个在它前面的比它大的数被挪到它后面去了，那么 val[i]--。

综合一下：一轮冒泡排序后，①如果 val[i]==0，则 val[i] 不变；②如果 val[i]>0，则 val[i]--。于是可以得到，经过 $k$ 轮冒泡排序后，val[i]=max(0,val[i]-k)。

那么我们可以这样回答询问“进行 $k$ 轮冒泡排序”：找到大于（大于等于也一样） $k$ 的所有 val[i] 的和记为 sum、以及有多少个这样的 val[i] 记为 cnt——那么答案就是 sum-k*cnt。这个简单，预处理一下 val[]（$O(n\log n)$ 逆序对），然后把 val[i] 前缀和（把权值作为下标来前缀和，类似于权值线段树）一下就好了~

但是还有修改操作。其实不难，假如要交换 $x,x+1$，显然 $x$ 之前或 $x+1$ 之后的位置的 val[] 没有影响。于是分类讨论（下面的 num[x] 和 num[x+1] 指交换过后对应的值）：

  1. num[x]>num[x+1]：那么 val[x+1] 比原来增加 1；
  2. num[x]<num[x+1]：那么 val[x] 比原来减少 1；

> Hint

这里务必注意 val[i] 的定义是“在 i 之前的比 num[i] 大的位置的个数”

我们发现，我们要求能够单点修改，查询前缀和……那不是树状数组就好了？

最后，还有一个坑，注意到查询的“进行$k$轮冒泡排序”中 $k$ 可以远大于 $n$，显然不能硬算，但是当 $k>n$ 时，整个数组已经排好了，那么就没有逆序对了。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=2e5;
#define lowbit(x) ((x)&-(x))

int n,m;
int num[N+3],tre[N+3],ini[N+3];
ll tres[N+3];

void Update(int pos,int val){
	while(pos<=n){
		tre[pos]+=val;
		pos+=lowbit(pos);
	}
}
void UpdateS(int val,int tmp){
	int pos=val+1;
	while(pos<=n){
		tre[pos]+=tmp;
		tres[pos]+=val*tmp;
		pos+=lowbit(pos);
	}
}
int Query(int pos){
	int ret=0;
	while(pos){
		ret+=tre[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
pair<int,ll> QueryS(int val){
	int pos=val+1;
	pair<int,ll> ret(0,0);
	while(pos){
		ret.first+=tre[pos];
		ret.second+=tres[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
		ini[i]=i-1-Query(num[i]);
		Update(num[i],1);
	}
	memset(tre,0,sizeof tre);
	for(int i=1;i<=n;i++)
		UpdateS(ini[i],1);
	while(m--){
		int cmd,x;scanf("%d%d",&cmd,&x);
		if(cmd==1){
			swap(num[x],num[x+1]);
			swap(ini[x],ini[x+1]);
			if(num[x]>num[x+1]){
				UpdateS(ini[x+1],-1);
				ini[x+1]++;
				UpdateS(ini[x+1],1);
			}
			else{
				UpdateS(ini[x],-1);
				ini[x]--;
				UpdateS(ini[x],1);
			}
		}
		else{
			if(x>n) printf("0\n");
			else{
				pair<int,ll> ret1=QueryS(n-1),ret2=QueryS(x-1);
				ll prtA=ret1.first-ret2.first;
				ll prtB=ret1.second-ret2.second;
				printf("%lld\n",prtB-prtA*x);
			}
		}
	}
	return 0;
}

# 赛场情况

我相当于是把 val[i] 定义为在 i 后面的比 num[i] 小的位置的数量……然后根本没发现任何规律——这种定义下，只有“移动”（就是文章中的图示中的“移动”了的位置）的 val[] 会减小，而且减小的值是移动的距离。

另外一个同学做出了正解，但是忽略了 $k>n$ 的这种情况。他写的权值线段树（实际上也可以），在这种情况下会死递归，然后就爆栈，洛谷的民间数据挂的很惨……不知道官方数据有没有可能。

The End

Thanks for reading!

“谁马踏桃花 画角长吟金鼓铿锵 寸土不让 万军一剑挡” - 《万古生香》