本题

伟大的 carotrl 在 AH 省集中提出冒泡排序若干轮之后的结果是可以直接刻画的。

具体来说说前缀 $[1,l]$ 在经过 $c$ 轮冒泡排序之后的数字构成是原先区间 $[1,l+c]$ 中的前 $l$ 小的数，这个很好理解，经过 $c$ 轮冒泡排序之后，某个数最多往前平移的位置数就是 $c$，所以范围是 $[1,l+c]$，而小的数会往前走，所以就是前 $l$ 小。

这样子就可以完成本题了，我们直接拿 $[1,r]$ 经过 $c$ 轮冒泡排序之后的数字组成减去 $[1,l-1]$ 的即可。区间 kth 信息可以直接拿主席树在线维护。时间复杂度 $O(n\log n)$。

扩展版-区间前 $k$ 小之和

改为若干次操作之后区间 $[l,r]$ 的前 $k$ 小值，如何做？

将上述定理扩展一些，前缀 $[1,l]$ 经过冒泡排序 $c$ 轮之后的前 $k$ 小值为原序列中区间 $[1,l+c]$ 的前 $k$ 小值。

区间 $[l,r]$ 经过 $c$ 轮冒泡排序之后的前 $k$ 小值就是前缀 $[1,r+c-1]$ 中去除前缀 $[1,l+c-1]$ 中的前 $l-1$ 小值之后的前 $k$ 小值，注意这里不能单纯拿两个作差，需要巧妙实现。

还是可以通过主席树在线维护的。本质还是对于两个前缀进行差分，需要设置一个阈值，意思是 $[1,l+c-1]$ 这个区间最多贡献 $l-1$。具体可以看看代码。

调用 solve(rt[min(l+c-1,n)],rt[min(r+c,n)],1,n,l-1,k) 即可，其中 $\rm query$ 函数就是对于某个版本的主席树区间求和。

	ll solve(int p,int q,int l,int r,int up,int cnt){
		if(l==r) return 1ll*cnt*l;
		int z=val[ls[q]]-min(val[ls[p]],up);
		if(z>=cnt) return solve(ls[p],ls[q],l,mid,up,cnt);
		int del=min(up,val[ls[p]]);
		return sum[ls[q]]-query(0,ls[p],l,mid,del)+solve(rs[p],rs[q],mid+1,r,up-del,cnt-z);
	}

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int a[maxn],b[maxn],rt[maxn],n,m,q;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct SegmentTree{
	#define mid ((l+r)>>1)
	int val[maxn<<6],ls[maxn<<6],rs[maxn<<6],tot; ll sum[maxn<<6];
	void pushup(int p){ val[p]=val[ls[p]]+val[rs[p]]; sum[p]=sum[ls[p]]+sum[rs[p]]; }
	void build(int &p,int q,int l,int r,int x){
		p=++tot; ls[p]=ls[q]; rs[p]=rs[q];
		val[p]=val[q]; sum[p]=sum[q]; 
		if(l==r){ val[p]++; sum[p]+=b[x]; return ; }
		if(x<=mid) build(ls[p],ls[q],l,mid,x);
		else build(rs[p],rs[q],mid+1,r,x);
		pushup(p);
	}
	ll query(int p,int q,int l,int r,int k){
		if(l==r) return 1ll*k*b[l]; 
		int z=val[ls[q]]-val[ls[p]];
		if(z>=k) return query(ls[p],ls[q],l,mid,k);
		else return sum[ls[q]]-sum[ls[p]]+query(rs[p],rs[q],mid+1,r,k-z);
	}
}seg;
int main(){
	cin>>n; int c=0;
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
	sort(b+1,b+1+n); m=unique(b+1,b+1+n)-(b+1); cin>>q;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
	for(int i=1;i<=n;i++) seg.build(rt[i],rt[i-1],1,m,a[i]);
	for(int i=1;i<=q;i++){
		int t,l,r; t=read();
		if(t==1) c++;
		else{
			l=read(); r=read();
			printf("%lld\n",seg.query(rt[0],rt[min(r+c,n)],1,m,r)-seg.query(rt[0],rt[min(l+c-1,n)],1,m,l-1));
		}
	}
	return 0;
}