专栏文章

【MGVOI R1-B】完美重排 题解

FFruitWasTaken
P13730题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioh0tnw
此快照首次捕获于
2025/12/02 19:04
3 个月前
此快照最后确认于
2025/12/02 19:04
3 个月前
查看原文

出题人题解

主要知识点

  • 【2】乘法原理
  • 【3】递推法
  • 【3】前缀和
  • 【3】冒泡排序

Subtask 1：测试点 1∼6\bm{1\sim 6}

直接枚举 LL 和 RR 然后 std::sort() 模拟即可，时间复杂度 O(Q⋅n3log⁡n)O(Q\cdot n^3 \log n)。

Subtask 2：测试点 7∼12\bm{7\sim 12}

考虑优化 Subtask 1 的做法至 O(Q⋅n2)O(Q\cdot n^2)。
我们发现，假设刚计算完对区间 [L,R][L,R] 进行完美重排后，原先下标为 xix_i 的数的新位置为 ziz_i（显然应满足 L≤xi≤RL\le x_i \le R，否则 xix_i 不在重排区间内），那么接下来枚举区间 [L,R+1][L,R+1] 时，还用重新模拟一遍排序吗？
实际上没必要。由于我们只关心原先下标为 xix_i 的数（记为 mm）在重排后的位置，所以可以由 [L,R][L,R] 这个区间的情况直接递推到 [L,R+1][L,R+1]：
  • 若 aR+1<ma_{R+1}<m，则 ziz_i 的值增加 11；
  • 若 aR+1>ma_{R+1}>m，则 ziz_i 的值不变。
模拟一下发现是很好理解的，因为当 aR+1<ma_{R+1}<m 时，重排区间新加入的 aR+1a_{R+1} 这个元素由于比 mm 更小，在排序后将 mm “顶”到了后面一个位置（类比冒泡排序）；而 aR+1>ma_{R+1}>m 时，对 mm 的位置则没有贡献。
同理，也可以由区间 [L,R][L,R] 的情况（L≤xi≤RL\le x_i \le R）递推到区间 [L−1,R][L-1,R]：
  • 若 aL−1>ma_{L-1}>m，则 ziz_i 的值减小 11（将 aL−1a_{L-1} 纳入重排区间后，mm 被向前“推”了一个位置）；
  • 若 aL−1<ma_{L-1}<m，则 ziz_i 的值不变。
综上，我们只需用双重循环枚举 L,RL,R，并按上述规则实时维护 ziz_i，就能 O(1)O(1) 地得出每个区间的答案，时间复杂度 O(Q⋅n2)O(Q\cdot n^2)。

Subtask3： 测试点 13∼20\bm{13\sim 20}

考虑将时间复杂度优化至 O(Q⋅n)O(Q\cdot n)。
承 Subtask 2，我们只关心 mm 的位置，于是考虑将数组 aa 重新扫一遍，得到一个新数组 bb：
  • 情况 1：若 j<xij<x_i 且 aj>ma_j>m，则 bj=−1b_j=-1；
  • 情况 2：若 j>xij>x_i 且 aj<ma_j<m，则 bj=+1b_j=+1；
  • 其它情况，bj=0b_j=0。
数组 bb 的意义是什么呢？类比上一个 Subtask 的区间递推，我们发现和之前一样，情况 1 可以等效成将 aja_j 纳入重排区间后，将 mm 向前“推”了一位；而情况 2 可以等效成将 aja_j 纳入重排区间后，将 mm 向后“顶”了一位。
那么可以观察到：对区间 [L,R][L,R] 进行完美重排之后（L≤xi≤RL\le x_i\le R），mm 对应的下标就是 xi+∑j=LRbjx_i+\sum\limits_{j=L}^R b_j，这就很清晰了!
于是就等价于问你在值域为 {−1,0,1}\{ -1,0,1 \} 的数组 bb 中，有多少对 (L,R)(L,R) 满足 bL+...+bR=yi−xib_L+...+b_R=y_i-x_i，并且 L≤xi≤RL\le x_i\le R。
一种做法是你可以算出 bb 的前缀和 b′b'，化为 bR′−bL−1′=yi−xib'_R-b'_{L-1}=y_i-x_i，然后这就变成了一个 A - B 数对模板题。当然，我们这里还是采取另一种做法，充分利用一下值域为 {−1,0,1}\{ -1,0,1 \} 的特性，具体地：
  • 第一步，记录 xix_i 之前所有 −1-1 的位置和 xix_i 之后所有 +1+1 的位置。显然，每两个相邻的 −1-1 （或每两个相邻的 +1+1）之间会隔若干个 00。
  • 第二步，根据上述分析，在我们选出的区间中，+1+1 的个数要恰好比 −1-1 的个数多 yi−xiy_i-x_i。那么直接枚举 −1-1 取多少个，这样 +1+1 取多少个也就确定了。
  • 第三步，确定了 +1+1 和 −1-1 取多少个之后，只需再用乘法原理统计一下它们后面 / 前面的 00 要怎么选。之前已经记录过所有 −1-1 和 +1+1 的位置，注意细节实现一下即可。
时间复杂度 O(Q⋅n)O(Q\cdot n)。
注：考虑到这只是 T2，所以并没有卡常数优秀的 O(Q⋅nlog⁡n)O(Q\cdot n \log n) 做法。

代码

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, Q, a[15005];
int x, y;
int L[15005], R[15005];

void solve()
{
	cin >> n >> Q;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	while (Q--)
	{
		cin >> x >> y;
		
		int index = x, cntL = 0, cntR = 0;
		
		while (index <= n)
		{
			if (a[index] < a[x])
				R[++cntR] = index;
			
			++index;
		}
		
		index = x;
		while (index >= 1)
		{
			if (a[index] > a[x])
				L[++cntL] = index;
			
			--index;
		}
		
		L[0] = R[0] = x;
		L[cntL + 1] = 0, R[cntR + 1] = n + 1;
		
		int ans = 0;
		for (int i = 0; true; i++)
		{
			if (y - x + i > cntR || i > cntL)
				break;
			
			ans += (R[y - x + i + 1] - R[y - x + i]) * (L[i] - L[i + 1]);
		}
		
		cout << ans << '\n';
	}
	
	return;
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	
	int _ = 1;
	while (_--)
	{
		solve();
	}
	
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...