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

FruitWasTaken · 2025-08-07 18:54:45 · 题解

出题人题解

主要知识点

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

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

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

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

考虑优化 Subtask 1 的做法至 O(Q\cdot n^2)。

我们发现，假设刚计算完对区间 [L,R] 进行完美重排后，原先下标为 x_i 的数的新位置为 z_i（显然应满足 L\le x_i \le R，否则 x_i 不在重排区间内），那么接下来枚举区间 [L,R+1] 时，还用重新模拟一遍排序吗？

实际上没必要。由于我们只关心原先下标为 x_i 的数（记为 m）在重排后的位置，所以可以由 [L,R] 这个区间的情况直接递推到 [L,R+1]：

若 a_{R+1}<m，则 z_i 的值增加 1；
若 a_{R+1}>m，则 z_i 的值不变。

模拟一下发现是很好理解的，因为当 a_{R+1}<m 时，重排区间新加入的 a_{R+1} 这个元素由于比 m 更小，在排序后将 m “顶”到了后面一个位置（类比冒泡排序）；而 a_{R+1}>m 时，对 m 的位置则没有贡献。

同理，也可以由区间 [L,R] 的情况（L\le x_i \le R）递推到区间 [L-1,R]：

若 a_{L-1}>m，则 z_i 的值减小 1（将 a_{L-1} 纳入重排区间后，m 被向前“推”了一个位置）；
若 a_{L-1}<m，则 z_i 的值不变。

综上，我们只需用双重循环枚举 L,R，并按上述规则实时维护 z_i，就能 O(1) 地得出每个区间的答案，时间复杂度 O(Q\cdot n^2)。

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

考虑将时间复杂度优化至 O(Q\cdot n)。

承 Subtask 2，我们只关心 m 的位置，于是考虑将数组 a 重新扫一遍，得到一个新数组 b：

情况 1：若 j<x_i 且 a_j>m，则 b_j=-1；
情况 2：若 j>x_i 且 a_j<m，则 b_j=+1；
其它情况，b_j=0。

数组 b 的意义是什么呢？类比上一个 Subtask 的区间递推，我们发现和之前一样，情况 1 可以等效成将 a_j 纳入重排区间后，将 m 向前“推”了一位；而情况 2 可以等效成将 a_j 纳入重排区间后，将 m 向后“顶”了一位。

那么可以观察到：对区间 [L,R] 进行完美重排之后（L\le x_i\le R），m 对应的下标就是 x_i+\sum\limits_{j=L}^R b_j，这就很清晰了!

于是就等价于问你在值域为 \{ -1,0,1 \} 的数组 b 中，有多少对 (L,R) 满足 b_L+...+b_R=y_i-x_i，并且 L\le x_i\le R。

一种做法是你可以算出 b 的前缀和 b'，化为 b'_R-b'_{L-1}=y_i-x_i，然后这就变成了一个 A - B 数对模板题。当然，我们这里还是采取另一种做法，充分利用一下值域为 \{ -1,0,1 \} 的特性，具体地：

第一步，记录 x_i 之前所有 -1 的位置和 x_i 之后所有 +1 的位置。显然，每两个相邻的 -1 （或每两个相邻的 +1）之间会隔若干个 0。
第二步，根据上述分析，在我们选出的区间中，+1 的个数要恰好比 -1 的个数多 y_i-x_i。那么直接枚举 -1 取多少个，这样 +1 取多少个也就确定了。
第三步，确定了 +1 和 -1 取多少个之后，只需再用乘法原理统计一下它们后面 / 前面的 0 要怎么选。之前已经记录过所有 -1 和 +1 的位置，注意细节实现一下即可。

时间复杂度 O(Q\cdot n)。

注：考虑到这只是 T2，所以并没有卡常数优秀的 O(Q\cdot n \log n) 做法。

代码

#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;
}

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