题意简述

给定 $n, m, k$（$m < k$），构造一个 $1 \sim n$ 的排列 $p$，定义：

• $f(i)$ = 前缀 $p[1..i]$ 中所有 $\ge k$ 的元素之和；
• $g(i)$ = 前缀 $p[1..i]$ 中所有 $\le m$ 的元素之和。

最大化 $\sum_{i=1}^n f(i) - \sum_{i=1}^n g(i)$，输出任意一个能取到最大值的排列。

贡献分析

对于排列中的每个元素 $x$，若它位于位置 $pos$（从 $1$ 开始），它会出现在所有 $i \ge pos$ 的前缀中。因此：

• 若 $x \ge k$，它对 $\sum f$ 的贡献为 $x \cdot (n - pos + 1)$；
• 若 $x \le m$，它对 $\sum g$ 的贡献为 $x \cdot (n - pos + 1)$（在差值中贡献为负）；
• 若 $m < x < k$，则对两个和都没有贡献。

总差值 $D = \sum_{x \ge k} x \cdot w(pos) - \sum_{y \le m} y \cdot w(pos)$，其中权重 $w(pos) = n - pos + 1$ 随位置靠前增大。

最大化策略

根据排序不等式，要使正项最大，应该让更大的 $x$ 搭配更大的权重（更靠前的位置），即把所有 $\ge k$ 的数按降序放在序列的最前面。

要使负项（减去 $y \cdot w$）尽可能小（即整体差值更大），应该让更小的 $y$ 搭配较大的权重，或者等价地，把所有 $\le m$ 的数按升序放在序列的最后面（这样较小的 $y$ 会相对靠前，权重稍大，但整体求和更小；详细推导见附注）。位于 $m$ 和 $k$ 之间的数字可以任意放置。

因此构造方案如下：

1. 先输出所有 $\ge k$ 的数，从大到小；
2. 再输出所有满足 $m < x < k$ 的数，顺序任意；
3. 最后输出所有 $\le m$ 的数，从小到大。

可以证明该构造能取到理论最大差值。

附注：坏数排序的简易证明

设两个坏数 $a < b$，两个权重 $w_1 > w_2$（靠前权重大）。分配方案：

• 方案一：$a \cdot w_1 + b \cdot w_2$
• 方案二：$a \cdot w_2 + b \cdot w_1$

方案一减去方案二 $= (a-b)(w_1-w_2) < 0$，故方案一的和更小。因此在坏数区域内，按升序排列（小的相对靠前）能使负项之和最小。

时间复杂度 $O(n)$，总复杂度 $O(\sum n)$，满足要求。

参考代码

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

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    // 第一部分：>= k 的数降序
    for (int i = n; i >= k; --i)
        cout << i << ' ';

    // 第二部分：m < x < k 的数，任意顺序
    for (int i = m + 1; i < k; ++i)
        cout << i << ' ';

    // 第三部分：<= m 的数升序
    for (int i = 1; i <= m; ++i)
        cout << i << ' ';

    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}