【2025NOI模拟赛12】冒泡排序 做题记录

给定 $n,k$ 和一个 $n$ 的排列 $p$，求下列代码中有效的 sort 被执行了几次：

while(1)
{
    bool f=true;
    for(int i=1;i<=n&&f;i++) f&=p[i]==i;
    if(f) break;
    for(int i=1;i<=n-k+1;i++) sort(p+i,p+i+k);
}

一次 sort 有效当且仅当其改变了 $p$。

$1\le n\le 2\times 10^5$，$2\le k\le n$。

设 $b_i$ 表示 $\sum\limits_{j=1}^{i-1}[a_j>a_i]$。

考虑若 $i\not=1$，则将 $[i,i+k-1]$ 排序的过程可以看作一个长 $k$ 的滑动窗口，每次把最小的数吐出来，然后喂进去一个数。

那么当区间右端点在 $r$ 时，窗口中的数就是 $[1,r]$ 中的前 $k$ 大值，故加入 $r+1$ 后 $b_{r+1}$ 会变成 $\max(b_{r+1}-(k-1),0)$。

排好序当且仅当所有 $b_i$ 都为 $0$，那么答案大概就是 $\sum\limits_i \lceil\frac{b_i}{k-1}\rceil$。

但是这样会比实际答案多，因为 $i=1$ 时会同时将 $b_{[1,k]}$ 变为 $0$，那么对于有可能去到 $[1,k]$ 的元素 $i$，先将答案加上 $\lceil\frac{b_i}{k-1}\rceil-1$，开个桶记录一下每一轮的 sort(p+1,p+k+1) 是否有效，最后再统计。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=200005;

int n,k,a[S];
int c[S],b[S],t[S];
bool flg[S];

inline void add(int p,int x)
{
	for(int i=p;i<=n;i+=i&-i) c[i]+=x;
}

inline int que(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=c[i];
	return res;
}

int main()
{
	freopen("bsort.in","r",stdin);
	freopen("bsort.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		add(a[i],1);
		b[i]=i-que(a[i]);
		t[i]=b[i]/(k-1)+!!(b[i]%(k-1));
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		if(t[i]>0)
		{
			if(i-(k-1)*(t[i]-1)<=k)
			{
				ans+=t[i]-1;
				flg[t[i]]=true;
			}
			else ans+=t[i];
		}
	}
	for(int i=1;i<=n;i++) ans+=flg[i];
	printf("%lld\n",ans);
	return 0;
}