题解：P13730 【MGVOI R1-B】完美重排（sort）

wangshengyue · 2025-08-16 22:04:08 · 题解

题目分析

题目要求计算：对数组进行恰好一次"完美重排"（选择区间 [ L , R ] 并排序）后，使原下标x的元素移动到下标y的方案数。关键条件：

• 区间 [ L , R ] 必须包含 x 和 y（即 L≤x 且 R≥y ，因 x<y ）
• 排序后元素在区间内的位置由"区间内小于它的元素数量"决定

不同复杂度解法对比

1. O(N³logN*q) 解法（纯暴力）

for each query(x,y):
    v = a[x]
    count = 0
    for L=1 to x:
        for R=y to n:
            复制a[L..R]并排序
            if 排序后v在位置y:
                count++
    output count

• 思路：枚举所有可能的 [ L , R ] ，对每个区间实际排序后检查条件

• 缺点：重复排序操作过多，效率极低

2. O(N³*q) 解法（优化排序）

for each query(x,y):
    v = a[x]
    count = 0
    for L=1 to x:
        for R=y to n:
            k = 区间[L..R]中小于v的元素数
            if L + k == y:  // 排序后v的位置公式
                count++
    output count

• 思路：用直接计数替代排序，通过"区间内小于 v 的元素数 k "判断位置（排序后 v 在 L+k 处）

• 优化点：利用"排序后位置=区间起点+区间内小于该元素的数量"这一数学关系

3. O(N²*q) 解法（前缀和优化）

for each query(x,y):
    v = a[x]
    预处理前缀和p[i] = [1..i]中小于v的元素数
    count = 0
    for L=1 to x:
        for R=y to n:
            k = p[R] - p[L-1]  // 区间[L..R]中小于v的数量
            if L + k == y:
                count++
    output count

• 思路：用前缀和数组 p 快速计算区间内小于 v 的元素数，避免每次遍历区间

• 关键：前缀和 p[i] 存储 [1..i]中小于v的元素总数，区间 [L..R] 的数量为 p[R]-p[L-1]

4. O(NlogN*q) 解法（二分查找优化）

for each query(x,y):
    v = a[x]
    预处理前缀和p[i] = [1..i]中小于v的元素数
    count = 0
    for L=1 to x:
        need = y - L  // 所需小于v的元素数
        target = need + p[L-1]
        // 在p[y..n]中找等于target的数量（二分）
        count += upper_bound(p[y..n], target) - lower_bound(p[y..n], target)
    output count

• 思路：固定 L 后，将R的枚举转为二分查找。对于每个 L ，满足条件的 R 需使 p[R] = target

• 核心：利用前缀和数组的单调性（非递减），通过二分快速定位符合条件的R范围，时间复杂度足以AC

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,q;  // n:数组长度，q:查询次数
    cin>>n>>q;
    vector<int> a(n+5,0);  // 存储原数组(1-based索引)
    vector<int> p(n+5,0);  // 用于存储前缀和(每个查询单独计算)

    // 读入数组元素
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    // 处理每组查询
    while(q--){
        int x,y;  // 查询参数：原位置x，目标位置y
        cin>>x>>y;
        int d = a[x];  // d为原x位置的元素值

        // 计算前缀和数组p：p[i]表示[1..i]中小于d的元素个数
        for(int i=1;i<=n;i++){
            p[i] = p[i-1] + (a[i] < d);  // 累加计数
        }

        long long ans = 0;  // 存储当前查询的答案

        // 枚举所有可能的L(L<=x，因x必须在[L,R]区间内)
        for(int l=1;l<=x;l++){
            // 计算目标前缀和：需要[L..R]中小于d的元素数为(y - l)
            // 因此p[R] = (y - l) + p[L-1]
            int target = (y - l) + p[l-1];

            // 在p[y..n]中查找等于target的元素个数
            // lower_bound找到第一个>=target的位置
            auto l1 = lower_bound(p.begin() + y, p.begin() + n + 1, target);
            // upper_bound找到第一个>target的位置
            auto r1 = upper_bound(p.begin() + y, p.begin() + n + 1, target);

            // 两个迭代器的差即为符合条件的R的数量
            ans += (r1 - l1);
        }

        // 输出当前查询的结果
        cout<<ans<<"\n";
    }
    return 0;//完美结束
}