题解

题目分析

给定数组 $a$，需要恰好选择一个区间 $[l,r]$，把这个区间循环左移一位，也就是把 $a_l$ 移到位置 $r$，中间的元素整体向左挪一格。目标是让操作后的逆序对数量最小。

关键点是：一次操作只改变 $a_l$ 和区间中其它元素之间的相对顺序。区间外的元素相对顺序不变；区间内部除 $a_l$ 以外的元素之间，相对顺序也不变。

从暴力到正解

最直接的暴力做法是枚举 $l,r$，真的构造操作后的数组，再统计逆序对数量。一次统计需要 $O(n^2)$，区间有 $O(n^2)$ 个，总复杂度为 $O(n^4)$，显然无法通过 $n\le 2000$。

进一步观察操作本身。选择 $[l,r]$ 后，只有 $a_l$ 被移到了 $r$，因此只有它和 $a_{l+1},a_{l+2},\ldots,a_r$ 的逆序关系可能改变。

对于某个 $i$，其中 $l<i\le r$：

• 操作前，$a_l$ 在 $a_i$ 前面，如果 $a_l>a_i$，这一对贡献 $1$ 个逆序对；
• 操作后，$a_i$ 在 $a_l$ 前面，如果 $a_i>a_l$，这一对贡献 $1$ 个逆序对；
• 如果二者相等，无论前后都不贡献逆序对。

所以这一对对逆序对数量变化量的贡献为：

• 若 $a_i>a_l$，变化量为 $+1$；
• 若 $a_i<a_l$，变化量为 $-1$；
• 若 $a_i=a_l$，变化量为 $0$。

于是对固定的 $l$，从左到右扩展 $r$，维护

$$\#\{i\mid l<i\le r,\ a_i>a_l\}-\#\{i\mid l<i\le r,\ a_i<a_l\}$$

即可得到选择这个 $[l,r]$ 后逆序对数量的变化量。原数组逆序对数量是固定的，因此只需要让这个变化量最小。

如果所有长度大于 $1$ 的区间变化量都不小于 $0$，那么选择 $l=r$，变化量为 $0$，就是最优答案。

正解思路

枚举左端点 $l$。对每个 $l$，令 greater_cnt 表示当前区间中大于 $a_l$ 的元素个数，less_cnt 表示小于 $a_l$ 的元素个数。然后枚举右端点 $r=l+1,\ldots,n$：

1. 根据 $a_r$ 和 $a_l$ 的大小关系更新两个计数；
2. 当前变化量为 greater_cnt - less_cnt；
3. 如果这个变化量比目前记录的最优值更小，就更新答案。

初始答案设为 $(1,1)$，变化量为 $0$，自然覆盖数组已经有序或不值得移动的情况。

正确性说明

选择区间 $[l,r]$ 后，除 $a_l$ 以外的所有元素相对顺序都没有改变，所以它们之间的逆序对数量不变；区间外元素和区间内元素的相对位置也没有跨越变化，只有 $a_l$ 与 $a_{l+1},\ldots,a_r$ 的相对顺序发生反转。

对每个 $i\in(l,r]$，若 $a_i>a_l$，操作前这对不是逆序对，操作后变成逆序对，变化量为 $+1$；若 $a_i<a_l$，操作前是逆序对，操作后不是，变化量为 $-1$；若相等，变化量为 $0$。因此区间 $[l,r]$ 的总变化量正是上述计数差。

算法枚举了所有可能的 $l$，并对每个 $l$ 枚举了所有 $r\ge l$ 的有效区间变化量，其中 $l=r$ 的变化量由初始答案 $0$ 覆盖。因此算法一定能找到使逆序对数量最小的区间。

复杂度分析

双重循环枚举所有区间，时间复杂度为 $O(n^2)$。题目保证所有测试用例的 $n^2$ 之和不超过 $4\cdot 10^6$，因此可以通过。

除输入数组外只使用常数个变量，空间复杂度为 $O(n)$。

参考代码（C++14）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;

    // 读入数组。
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // best 记录当前找到的最小逆序对变化量。
    // 初始选择长度为 1 的区间，变化量为 0。
    int best = 0;
    int ans_l = 0, ans_r = 0;

    // 枚举被移动到区间末尾的元素 a[l]。
    for (int l = 0; l < n; ++l) {
        int greater_cnt = 0; // 区间中比 a[l] 大的元素个数
        int less_cnt = 0;    // 区间中比 a[l] 小的元素个数

        // 逐步扩展右端点 r，并维护变化量。
        for (int r = l + 1; r < n; ++r) {
            if (a[r] > a[l]) {
                ++greater_cnt;
            } else if (a[r] < a[l]) {
                ++less_cnt;
            }

            int diff = greater_cnt - less_cnt;
            if (diff < best) {
                best = diff;
                ans_l = l;
                ans_r = r;
            }
        }
    }

    // 输出 1-based 下标。
    cout << ans_l + 1 << ' ' << ans_r + 1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}