题解：P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

Solution

什么是冒泡排序？

众所周知，在每一次遍历中，我们比较相邻的两个元素，并把更大的放到后面，这样可以保证每一次都将剩下元素中最大的一个扔到最后，所以保证了时间复杂度是

O(n^2)

。

这意味着，如果对于一个已经进行了

i

轮冒泡排序的序列来说，它的前

i

大元素会在最后，剩下的则在前面。

因此我们能够得到一个关键结论：对于一个已经进行了 $i$ 轮冒泡排序的序列，它的前 $j$ 个元素恰好是原序列中前 $i+j$ 个元素中的前 $j$ 小。

然后做完了。

每一次询问二，我们用当前序列的前

R

个减去前

(L-1)

个，这时就用到了上述的结论。这是主席树经典用法，类似树上二分，在静态区间第

k

小的基础上加上区间和即可。具体实现可见代码。

Code

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500005,M = 1000000000;
int n,a[N],q,cnt,root[N],tot;
struct node
{
	int w,ls,rs,sz;
}f[N<<5];
int update(int root,int l,int r,int x)
{
	f[cnt+1] = f[root];
	root = ++cnt;
	if (l >= r)
	{
		f[root].w += x;
		f[root].sz++;
		return root;
	}
	int mid = (l+r)/2;
	if (x <= mid) f[root].ls = update(f[root].ls,l,mid,x);
	else f[root].rs = update(f[root].rs,mid+1,r,x);
	f[root].w = f[f[root].ls].w+f[f[root].rs].w;
	f[root].sz = f[f[root].ls].sz+f[f[root].rs].sz;
	return root;
}
int query(int root,int l,int r,int k)
{
	if (!k) return 0;
	if (l >= r) return f[root].w/f[root].sz*k;
	int mid = (l+r)/2;
	if (f[f[root].ls].sz >= k) return query(f[root].ls,l,mid,k);
	return f[f[root].ls].w+query(f[root].rs,mid+1,r,k-f[f[root].ls].sz);
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		root[i] = root[i-1];
		root[i] = update(root[i],1,M,a[i]);
	}
	cin >> q;
	while (q--)
	{
		int op,l,r;
		cin >> op;
		if (op == 1) tot++;
		else
		{
			cin >> l >> r;
			cout << query(root[min(n,r+tot)],1,M,r)-query(root[min(n,l+tot-1)],1,M,l-1)<< '\n';
		}
	}
	return 0;
}

题解：P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

文章操作

Solution

Code

相关推荐

评论

题解：P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine