冒泡排序机 / Bubble Sort Machine JOI Open 2025

[JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

[JOI Open 2025] 冒泡排序机 / Bubble Sort Machine。

经验：[ICPC 2023 Seoul R] Apricot Seeds。

给定长度 $n$ 的数组 $a$，求冒泡排序第 $K$ 轮后区间 $[l,r]$ 的和。

$n\le 5\times 10^5$。

首先看到区间 $[l,r]$，先转化为前缀和 $[1,x]$。

然后考虑刻画冒泡排序的结果。

先看看冒泡排序第一轮的结果 $a'$。那么对于第 $1$ 个位置，显然排序后其值为 $\min\{a_1,a_2\}$。

然后是第二个位置。因为 $a'_1=\min\{a_1,a_2\}$，所以交换第一个数后 $a'_2=\max\{a_1,a_2\}$；然后又因为第二个数会和第三个数交换，于是 $a'_2=\min\{a_3,\max\{a_1,a_2\}\}$。

然后对于 $a_3$，由于冒泡排序的性质，最大的数总是在最后；因此交换前两个后 $a'_3=\max\{a_1,a_2,a_3\}$，然后交换第 $3,4$ 个，可得 $a'_3=\min\{a_4,\max\{a_1,a_2,a_3\}\}$。

由此，归纳可证：

引理 1：

冒泡排序第一轮的结果 $a'$ 满足：

$$a'_i=\min\{a_{i+1},\max_{1\le j\le i}\{a_j\}\}$$

考虑扩展这一想法。

显然对于 $a_1$，冒泡排序第 $K$ 轮的结果 $a'$ 满足 $a'_1=\min\{a_j\mid 1\le j\le K+1\}$。

然后，对于 $a_2$，第一轮 $a'$ 他会变为 $\min\{a_3,\max\{a_1,a_2\}\}$，第二轮 $a''$ 他就会迭代的变为：

$$\begin{aligned} a''_2&=\min\{a'_3,\max\{a'_1,a'_2\}\}\\ &=\min\{\min\{a_4,\max\{a_1,a_2,a_3\}\},\max\{\min\{a_1,a_2\},\min\{a_3,\max\{a_1,a_2\}\}\}\} \end{aligned}$$

归纳的，可证：

引理 2：

冒泡排序第 $K$ 轮的结果 $a^(K)$ 满足前 $x$ 项为原序列的前 $x+K$ 个数中前 $x$ 大的。

因此只需要可持久化线段树或者 Wavelet 就可以解决。

PS：如果还是看不懂引理 2 的归纳证明，可以简单理解为：$K$ 轮时前 $x$ 个数只会和前 $x+K$ 个数发生交互，然后由于冒泡排序的性质，后 $K$ 大的数会被弹出前 $x$ 个。

#include <bits/stdc++.h>
using namespace std;
const int N=500100,M=20000010;
using ll=long long;
int ls[M],rs[M],num[M],n,m,a[N],am[N],ss,rt[N],idx;
ll sum[M];
int build(int p,int l,int r){
	p=++idx;
	if(l==r)return p;
	int mid=(l+r)>>1;
	ls[p]=build(p,l,mid);
	rs[p]=build(p,mid+1,r);
	return p;
}
void copy(int x,int y){ls[x]=ls[y],rs[x]=rs[y],num[x]=num[y],sum[x]=sum[y];}
int insert(int p,int l,int r,int x){
	++idx,copy(idx,p),p=idx;
	if(l==r){
		num[p]++;
		sum[p]+=am[x];
		return p;
	}
	int mid=(l+r)>>1;
	if(mid>=x)ls[p]=insert(ls[p],l,mid,x);
	else rs[p]=insert(rs[p],mid+1,r,x);
	num[p]=num[ls[p]]+num[rs[p]];
	sum[p]=sum[ls[p]]+sum[rs[p]];
	return p;
}
ll query(int p,int l,int r,int x){
	if(l==r)return 1ll*am[l]*x;
	int mid=(l+r)>>1,k=num[ls[p]];
	if(k>=x)return query(ls[p],l,mid,x);
	return query(rs[p],mid+1,r,x-k)+sum[ls[p]];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i),am[++ss]=a[i];
	sort(am+1,am+1+ss);ss=unique(am+1,am+1+ss)-am-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(am+1,am+1+ss,a[i])-am;
	rt[0]=build(1,1,ss);
	for(int i=1;i<=n;i++)
		rt[i]=insert(rt[i-1],1,ss,a[i]);
	scanf("%d",&m);
	int K=0;
	while(m--){
		int opt,x,y;
		scanf("%d",&opt);
		if(opt==1)K++;
		else{
			scanf("%d%d",&x,&y);
			printf("%lld\n",-(x==0?0:query(rt[min(n,x-1+K)],1,ss,x-1))+
				query(rt[min(n,y+K)],1,ss,y));
		}
	}
	return 0;
}