AtCoder Beginner Contest 431 题解

for-each2026年8月18日大约 20 分钟

AtCoder Beginner Contest 431 题解

项目	内容
比赛时间	2025-11-08
比赛链接	https://atcoder.jp/contests/abc431
题目数量	A–G 共 7 题

比赛概览

本场以"机器人"为背景串联 A–D 四题：A、B 是基础语法题（分支判断、数组状态维护），C 是排序+贪心，D 是 01 背包 DP。E 需要把"镜子反射光线"建模成图并跑 01-BFS，F 是一道插入 DP + 组合数的计数题，G 则是基于字典序排序结构的困难题。整体难度适中，区分度主要落在 E、F、G 三题上，它们分别考察图形建模、对"可插入位置只与计数有关"的洞察，以及对交换后字典序结构的分析。

A - Robot Balance

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_a

题目大意

头重为 $H$ 克、身重为 $B$ 克，若头重大于身重机器人会倒。问至少需要让身体增加多少克，才能保证机器人不倒。输入一行 H B，输出最小增重量。

思路

机器人不倒当且仅当头重不超过身重。设身体增重 $x$ 克，则条件是 $H \le B + x$ ，即 $x \ge H - B$ 。因此最小增重量为

x = \max(H - B,\ 0) = \max(H, B) - B.

当 $H \le B$ 时答案为 $0$ ；否则答案为 $H - B$ 。注意头、身相等时机器人不会倒，所以判断用 $\le$ 而不是 $<$ 。实现上直接 if 分支即可，也可以用 max 一行求出。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int H, B;
    cin >> H >> B;
    cout << max(H, B) - B << endl;
    return 0;
}

官方题解同时给出了等价的分支写法与 Python 版本：

H, B = map(int, input().split())
print(max(H, B) - B)

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Robot Weight

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_b

题目大意

机器人初始重量为 $X$ ，共有 $N$ 种零件，第 $i$ 种零件的重量为 $W_i$ 。初始所有零件都未安装。按顺序处理 $Q$ 次操作，每次给出零件编号 $P_i$ ：若该零件当前未安装则安装它，否则拆除它，并输出操作后机器人的总重量。

思路

用一个布尔数组记录每种零件当前是否已安装。每次操作先翻转零件 $P_i$ 的状态，再输出总重量。总重量可以直接重算为"初始重量 + 所有已安装零件的重量和"，也可以维护一个当前总重变量：安装时 $+\ W_{P_i}$ ，拆除时 $-\ W_{P_i}$ ，这样每条查询只需 $O(1)$ 。由于 $N, Q \le 100$ ，两种写法均可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int X, N;
    cin >> X >> N;
    vector<int> W(N);
    for (int i = 0; i < N; ++i) cin >> W[i];

    vector<bool> on(N, false);
    int cur = X;

    int Q;
    cin >> Q;
    while (Q--) {
        int P;
        cin >> P;
        --P;
        if (on[P]) {
            on[P] = false;
            cur -= W[P];
        } else {
            on[P] = true;
            cur += W[P];
        }
        cout << cur << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(N + Q)$
空间复杂度： $O(N)$

C - Robot Factory

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_c

题目大意

有 $N$ 个头（重量 $H_i$ ）和 $M$ 个身体（重量 $B_j$ ）。每个机器人由一个头和一个身体组成，且头重不超过身重时机器人不会倒。每个零件最多使用一次。问能否恰好组装出 $K$ 个不倒的机器人。

思路

先把头、身体分别按重量升序排序：

H_1 \le H_2 \le \cdots \le H_N,\qquad B_1 \le B_2 \le \cdots \le B_M.

关键结论：若存在某种合法组装方案，那么"取最轻的 $K$ 个头与最重的 $K$ 个身体，按序一一配对"（即第 $i$ 轻的头配第 $i$ 轻的选中身体， $i=1,\dots,K$ ）也一定合法。因此只需检查是否对每个 $i$ 都有

H_i \le B_{M-K+i},

全部满足输出 Yes，否则输出 No。

为什么正确（交换论证）：

设某个合法方案用到的 $K$ 个头按重量升序为 $a_1 < a_2 < \cdots < a_K$ （下标按排序后的顺序），配对的 $K$ 个身体记为 $b_1, \dots, b_K$ 。由于第 $i$ 小的被用头在原序列中的位置至少是 $i$ （即 $a_i \ge i$ ），且 $H_i \le H_{a_i}$ ，所以把第 $i$ 个最轻的头与身体 $b_i$ 配对仍然合法。
把 $b$ 序列按重量升序重排为 $b'_1 \le \cdots \le b'_K$ ，并断言配对 $(i, b'_i)$ 仍全部合法。若不合法，存在相邻逆序对 $b'_i > b'_{i+1}$ ，我们来交换身体：因为 $H_i \le H_{i+1}$ 且原配对 $(i+1, b'_{i+1})$ 合法给出 $H_{i+1} \le B_{b'_{i+1}}$ ，故 $H_i \le B_{b'_{i+1}}$ ；又 $B_{b'_{i+1}} \le B_{b'_i}$ ，于是 $(i, b'_{i+1})$ 与 $(i+1, b'_i)$ 均合法。反复交换即可消去所有逆序对。
最后， $K$ 元子集的第 $i$ 小元素 $B_{b'_i}$ 不超过全体 $M$ 个身体中第 $M-K+i$ 小者 $B_{M-K+i}$ （理由：若某个 $K$ 子集的第 $i$ 小元素大于 $B_{M-K+i}$ ，则子集里至少有 $K-i+1$ 个元素大于 $B_{M-K+i}$ ，但大于它的位置总共只有 $K-i$ 个，矛盾）。故配对 $(i, M-K+i)$ 合法。

由"合法方案存在 $\Rightarrow$ 贪心方案合法"，反过来说贪心检查失败即说明任何方案都不可能。注意 $H_i \le B_j$ 取等时也合法。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<long long> H(N), B(M);
    for (int i = 0; i < N; ++i) cin >> H[i];
    for (int i = 0; i < M; ++i) cin >> B[i];

    sort(H.begin(), H.end());
    sort(B.begin(), B.end());

    for (int i = 0; i < K; ++i) {
        if (H[i] > B[M - K + i]) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

官方题解的 Python 写法同样简洁：

N, M, K = map(int, input().split())
H = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
print('Yes' if all(h <= b for h, b in zip(H[:K], B[-K:])) else 'No')

复杂度分析

时间复杂度： $O(N \log N + M \log M)$ （排序），检查部分 $O(K)$
空间复杂度： $O(N + M)$

D - Robot Customize

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_d

题目大意

有 $N$ 种零件，每种恰好一个且必须全部安装。第 $i$ 种零件的重量为 $W_i$ ，装在头上获得幸福度 $H_i$ ，装在身上获得幸福度 $B_i$ 。头的重量为所有装头零件重量之和，身的重量为所有装身零件重量之和；头重超过身重时机器人会倒。求在不倒的前提下，幸福度总和的最大值。

思路

设所有零件总重 $S = \sum_i W_i$ 。因为每个零件要么装头要么装身，所以 $头重 + 身重 = S$ ，不倒条件 $头重 \le 身重$ 等价于

头重 \le \frac{S}{2}\quad\Longleftrightarrow\quad 头重 \le \left\lfloor \frac{S}{2} \right\rfloor.

转化为 0/1 背包。 先把所有零件都放身上，总幸福度为 $\sum B_i$ ；再考虑把某些零件挪到头上去。若把零件 $i$ 挪到头上，幸福度变化 $V_i = H_i - B_i$ （可为正可为负），头重增加 $W_i$ 。于是问题变成：

背包容量 $C = \lfloor S/2 \rfloor$ ；
每个零件 $i$ 是一个物品，重量 $W_i$ 、价值 $V_i$ ；
在所选物品总重量不超过 $C$ 的前提下，最大化价值和 $E$ ；
答案 $= \sum B_i + E$ 。

DP 转移。 令 $dp_j$ 表示"头的总重量恰好为 $j$ 时， $V_i$ 之和的最大值"。因为 $V_i$ 可能为负，初始化 $dp_0 = 0$ ，其余为 $-\infty$ ；每个物品用倒序更新（0/1 背包避免重复选取）：

dp_j = \max(dp_j,\ dp_{j-W_i} + V_i)\qquad (j \text{ 从 } C \text{ 递减到 } W_i).

由于空集始终可行（ $dp_0 = 0$ ）， $E = \max_{0 \le j \le C} dp_j \ge 0$ 。 $N \le 500$ 、 $W_i \le 500$ ，故 $S \le 2.5\times 10^5$ ，复杂度 $O(NC) \le O(N \cdot S)$ 可行。幸福度总和最大可达 $500 \times 10^9 = 5\times 10^{11}$ ，需用 64 位整数。

参考代码

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

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

    int N;
    cin >> N;
    vector<int> W(N);
    vector<ll> H(N), B(N);
    ll sumB = 0, S = 0;
    for (int i = 0; i < N; ++i) {
        cin >> W[i] >> H[i] >> B[i];
        sumB += B[i];
        S += W[i];
    }

    int C = (int)(S / 2);              // 头部重量上限 floor(S/2)
    const ll NEG = -(1LL << 60);
    vector<ll> dp(C + 1, NEG);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        ll v = H[i] - B[i];
        for (int j = C; j >= W[i]; --j) {
            if (dp[j - W[i]] != NEG)
                dp[j] = max(dp[j], dp[j - W[i]] + v);
        }
    }

    ll best = 0;
    for (int j = 0; j <= C; ++j) best = max(best, dp[j]);
    cout << sumB + best << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \cdot S)$ ，其中 $S = \sum W_i \le 2.5\times 10^5$
空间复杂度： $O(S)$

E - Reflection on Grid

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_e

题目大意

有 $H\times W$ 的网格，每个格子摆放三种镜子之一：A（不放镜子，光直行）、B（沿主对角线摆放，即反斜杠 \）、C（沿副对角线摆放，即斜杠 /）。一束光从 $(1,1)$ 左侧水平向右射入，穿过每个格子时按该格镜子类型改变方向。每次操作可以把一个格子的镜子改成另外两种之一。问最少操作多少次，才能使光最终从 $(H,W)$ 的右侧射出（照到 Aoki）。多组测试。

思路

第一步：给方向编号。 用 $0,1,2,3$ 分别表示下、右、上、左，取 $dx=[1,0,-1,0]$ 、 $dy=[0,1,0,-1]$ 。这样光从格子 $(x,y)$ 以方向 $d$ 离开后进入的相邻格为 $(x+dx_d, y+dy_d)$ 。

第二步：把镜子的反射规则用异或描述。 设光以方向 dir 进入某格子，选择方向 ndir 离开。不能 180° 折返，即必须排除 dir ^ ndir == 2。三种镜子的自然反射对应：

类型 A（直行）：dir ^ ndir == 0；
类型 B（\）：右↔下、左↔上，即 dir ^ ndir == 1；
类型 C（/）：右↔上、左↔下，即 dir ^ ndir == 3。

由于 dir ^ ndir 的取值只有 $\{0,1,2,3\}$ ，排除 $2$ 之后恰好被三种镜子一一覆盖。因此：若 dir ^ ndir 恰等于当前格类型对应的异或值，光可以直接通过该格（代价 $0$ ）；否则需要把该格改成能实现该偏转的类型（代价 $1$ ，总能把三个类型改成需要的那个）。于是每个格子的"偏转操作"代价只可能是 $0$ 或 $1$ 。

第三步：建图跑 01-BFS。 定义状态 $(x, y, d)$ 为"光离开格子 $(x,y)$ 时方向为 $d$ "， $dp[x][y][d]$ 表示达到该状态所需的最小操作次数。从状态 $(x,y,d)$ 出发，光进入相邻格 $(nx,ny)$ （入射方向为 $d$ ），在该格内选择出射方向 $nd$ ，转移边权为 $0$ 或 $1$ 。所有边权只有 $0/1$ ，用双端队列 BFS（01-BFS）即可求出单源最短路：代价 $0$ 的松弛入队首，代价 $1$ 的松弛入队尾。

初始状态：光从 $(1,1)$ 左侧射入，即入射方向为右（ $1$ ），在处理完 $(1,1)$ 后得到初始 $dp[0][0][nd]$ 。答案取 $dp[H-1][W-1][1]$ ，即光从 $(H,W)$ 向右射出。

状态数 $4HW$ ，每个状态至多转移 $4$ 次，01-BFS 总复杂度 $O(HW)$ ；所有测试数据满足 $\sum HW \le 2\times 10^5$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int mirror(char c) {        // 每种镜子类型对应的 dir^ndir
    if (c == 'A') return 0;
    if (c == 'B') return 1;
    return 3;               // 'C'
}

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (auto &r : S) cin >> r;

    // dp[x][y][d] = 光离开 (x,y) 方向为 d 的最小操作次数
    vector<vector<array<int, 4>>> dp(H, vector<array<int, 4>>(W));
    for (auto &row : dp)
        for (auto &v : row) v.fill(INF);

    deque<tuple<int, int, int, int>> dq; // (x, y, d, cost)
    // 初始：光从 (1,1) 左侧射入，入射方向为右(1)
    for (int nd = 0; nd < 4; ++nd) {
        if ((1 ^ nd) == 2) continue;                    // 禁止折返
        int c = ((1 ^ nd) == mirror(S[0][0])) ? 0 : 1;
        if (c < dp[0][0][nd]) {
            dp[0][0][nd] = c;
            if (c == 0) dq.push_front({0, 0, nd, c});
            else dq.push_back({0, 0, nd, c});
        }
    }

    while (!dq.empty()) {
        auto [x, y, d, cost] = dq.front();
        dq.pop_front();
        if (dp[x][y][d] != cost) continue;              // 过期状态
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        for (int nd = 0; nd < 4; ++nd) {
            if ((d ^ nd) == 2) continue;
            int nc = cost + (((d ^ nd) == mirror(S[nx][ny])) ? 0 : 1);
            if (nc < dp[nx][ny][nd]) {
                dp[nx][ny][nd] = nc;
                if (nc == cost) dq.push_front({nx, ny, nd, nc});
                else dq.push_back({nx, ny, nd, nc});
            }
        }
    }
    cout << dp[H - 1][W - 1][1] << '\n';
}

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

官方题解仅给出了 Python 实现（思想与本代码完全一致，此处提供可移植的 C++ 版本）。

复杂度分析

时间复杂度： $O(HW)$ （01-BFS，状态数 $4HW$ 、转移数 $O(4HW)$ ；多组数据总规模 $\sum HW \le 2\times 10^5$ ）
空间复杂度： $O(HW)$

F - Almost Sorted 2

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_f

题目大意

给长度为 $N$ 的整数序列 $A$ 和正整数 $D$ 。求把 $A$ 重排（重新排列后得到的不同序列 $B$ ）中，满足对每个 $i$ 有 $B_{i+1} \ge B_i - D$ 的序列个数，答案对 $998244353$ 取模。

思路

关键转化。 条件 $B_{i+1} \ge B_i - D$ 即 $B_i - B_{i+1} \le D$ ：相邻两个数中，前一个不能比后一个大超过 $D$ 。换句话说，一个值为 $v$ 的元素前面不能紧跟着一个大于 $v+D$ 的元素（若 $x > v+D$ 放在 $v$ 前面，则 $v < x-D$ ，违反条件）。

插入 DP（按值从小到大逐个插入）。 按值从小到大地把元素插进序列。假设所有值小于 $v$ 的元素已经排好，现在要把 $\mathrm{cnt}[v]$ 个值为 $v$ 的元素插入。插入某个位置后会产生两对新的相邻关系 $(u, v)$ 和 $(v, w)$ ，其中 $u$ 、 $w$ 是插入位置前后的元素：

约束 $(u, v)$ ：要求 $v \ge u - D$ 即 $u \le v + D$ 。由于所有已排元素都小于 $v$ ，该条件自动满足；
约束 $(v, w)$ ：要求 $w \ge v - D$ 。

因此插入位置合法当且仅当其后的元素 $w$ 满足 $w \ge v - D$ 。开头的空位也要看其后第一个元素是否满足；而末尾的空位没有后继元素，永远合法。

于是合法空位的个数 = "值落在 $[v-D,\ v-1]$ 内的已排元素个数" $+1$ （末尾空位）——因为每个满足 $w \in [v-D, v-1]$ 的元素正好对应其前方的一个空位。例如 $D=3$ ，当前序列为 $(4,1,3,5,4,2,3)$ ，要插入 $v=6$ ：值在 $[3,5]$ 内的元素为 $4,3,5,4,3$ 共 $5$ 个，它们前方各有一个合法空位，再加上末尾空位，共 $5+1=6$ 个空位。

核心洞察：合法空位数只依赖计数，与当前序列的具体排列无关！ 它等于

\mathrm{cnt}[v-D] + \mathrm{cnt}[v-D+1] + \cdots + \mathrm{cnt}[v-1] + 1.

把 $\mathrm{cnt}[v]$ 个不可区分的 $v$ 放进这 $m+1$ 个可区分的空位（其中 $m = \sum_{u=v-D}^{v-1}\mathrm{cnt}[u]$ ），等价于把 $\mathrm{cnt}[v]$ 个相同小球放入 $m+1$ 个不同盒子，由隔板法知方案数为

\binom{m + \mathrm{cnt}[v]}{\mathrm{cnt}[v]} = \binom{\mathrm{cnt}[v-D] + \cdots + \mathrm{cnt}[v]}{\mathrm{cnt}[v]}.

因此答案为

\prod_{v=1}^{\max A} \binom{\mathrm{cnt}[v-D] + \cdots + \mathrm{cnt}[v]}{\mathrm{cnt}[v]} \pmod{998244353}.

正确性。 每个满足条件的序列 $B$ 有唯一的构造过程（按值从小到大、每个值占据唯一的空位组合），而每一步的插入方案数只依赖计数，所以各值的选择互相独立、乘积即总数。没有出现过的值 $\mathrm{cnt}[v]=0$ 对应 $\binom{s}{0}=1$ ，不改变答案，但滑动窗口仍需经过这些下标以维持窗口内容。

实现。 用滑动窗口维护 $s = \sum_{u=v-D}^{v} \mathrm{cnt}[u]$ ：从 $v=0$ 扫到 $\max A$ ，每步先 s += cnt[v]，乘上 $\binom{s}{\mathrm{cnt}[v]}$ ，然后若 $v \ge D$ 就 s -= cnt[v-D]。组合数用阶乘 + 费马小定理逆元预处理（上标 $s \le N$ ）。复杂度 $O(N + \max A)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

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

    int N;
    ll D;
    cin >> N >> D;
    vector<int> A(N);
    int maxA = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        maxA = max(maxA, A[i]);
    }

    vector<int> cnt(maxA + 1, 0);
    for (int x : A) cnt[x]++;

    vector<ll> fac(N + 1), ifac(N + 1);
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % MOD;
    ifac[N] = modpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; --i) ifac[i - 1] = ifac[i] * i % MOD;
    auto C = [&](ll n, ll k) -> ll {
        if (n < 0 || k < 0 || k > n) return 0;
        return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
    };

    ll ans = 1, s = 0;
    for (int v = 0; v <= maxA; ++v) {
        s += cnt[v];
        ans = ans * C(s, cnt[v]) % MOD;
        if ((ll)v >= D) s -= cnt[v - (int)D];
    }
    cout << ans << '\n';
    return 0;
}

官方题解给出了相同思路的 Python 实现（滑动窗口写法一致）：

MOD = 998244353
N, D = map(int, input().split())
A = list(map(int, input().split()))
lim = max(A)
cnt = [0] * (lim + 1)
for x in A:
    cnt[x] += 1

fac = [1] * (N + 1)
for i in range(2, N + 1):
    fac[i] = fac[i - 1] * i % MOD
ifac = [1] * (N + 1)
ifac[N] = pow(fac[N], MOD - 2, MOD)
for i in range(N, 0, -1):
    ifac[i - 1] = ifac[i] * i % MOD

def C(n, k):
    if n < 0 or k < 0 or k > n:
        return 0
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD

ans = 1
s = 0
for v in range(lim + 1):
    s += cnt[v]
    ans = ans * C(s, cnt[v]) % MOD
    if v >= D:
        s -= cnt[v - D]
print(ans)

复杂度分析

时间复杂度： $O(N + \max A)$ （ $N \le 2\times 10^5$ ， $\max A \le 10^6$ ）
空间复杂度： $O(N + \max A)$

G - One Time Swap 2

题目链接：https://atcoder.jp/contests/abc431/tasks/abc431_g

题目大意

给长度为 $N$ 的序列 $A$ 。对每一对 $l<r$ ， $f(l,r)$ 表示交换 $A_l$ 与 $A_r$ 后得到的序列。把所有这样的序列（共 $\frac{N(N-1)}{2}$ 个）按字典序排序得到 $B$ 。有 $Q$ 次询问，每次给 $k$ ，输出任意一对满足 $B_k = f(l,r)$ 的 $(l,r)$ 。

思路

核心观察：一次交换与 $A$ 的大小关系。 对 $l<r$ ：

若 $A_l > A_r$ ，则 $f(l,r) < A$ （字典序更小）；
若 $A_l = A_r$ ，则 $f(l,r) = A$ ；
若 $A_l < A_r$ ，则 $f(l,r) > A$ 。

于是排序后的 $B$ 被切成三段。设

D = \#\{l<r : A_l > A_r\},\qquad E = \#\{l<r : A_l = A_r\},\qquad U = \#\{l<r : A_l < A_r\},

则 $B$ 的前 $D$ 项都小于 $A$ ，接下来 $E$ 项都等于 $A$ ，最后 $U$ 项都大于 $A$ 。其中 $D$ 就是序列的逆序对数， $E = \sum_v \binom{\mathrm{cnt}[v]}{2}$ ， $U = \frac{N(N-1)}{2} - D - E$ 。根据 $k$ 落在哪一段，分别处理。

小于 $A$ 的一段内部的字典序排序。 对两个都满足 $A_{l_1} > A_{r_1}$ 、 $A_{l_2} > A_{r_2}$ 的对 $(l_1,r_1)$ 、 $(l_2,r_2)$ ， $f(l_1,r_1)$ 与 $f(l_2,r_2)$ 的字典序关系恰等于三元组 $(l_1, A_{r_1}, -r_1)$ 与 $(l_2, A_{r_2}, -r_2)$ 的字典序关系。证明分三类（假设 $l_1 \le l_2$ ）：

若 $l_1 < l_2$ ：前 $l_1-1$ 位相同，第 $l_1$ 位分别是 $A_{r_1}$ 与 $A_{l_1}$ ，而 $A_{r_1} < A_{l_1}$ ，故 $f(l_1,r_1)$ 更小；
若 $l_1 = l_2$ 且 $A_{r_1} \ne A_{r_2}$ ：第 $l_1$ 位分别是 $A_{r_1}$ 、 $A_{r_2}$ ，顺序由两者大小决定；
若 $l_1 = l_2$ 且 $A_{r_1} = A_{r_2}$ （此时 $r_1 < r_2$ ）：前 $r_1 - 1$ 位相同，第 $r_1$ 位分别是 $A_{l_1}$ 与 $A_{r_1}$ ，因 $A_{l_1} > A_{r_1}$ ，故 $f(l_1,r_1)$ 更大，即 $r$ 较大的排前面。

大于 $A$ 的一段同理，排序对应三元组 $(-l, A_r, r)$ ；等于 $A$ 的一段所有序列相同，输出任意一对 $A_l = A_r$ 即可。

算法流程。 需要一个支持"求当前集合中第 $k$ 小"与"统计小于某个值的元素个数"的数据结构。这里用树状数组 + 坐标压缩实现（把 $(A_j, \pm j)$ 压成排名，再用树状数组求前缀和与二分查找第 $k$ 小），完全可移植。

小于 $A$ 的一段：把询问按 $k$ 升序排序。从左到右扫描 $l$ ，数据结构维护所有 $j > l$ 的 $(A_j, -j)$ 。对于固定 $l$ ，其贡献的 $D$ 类对按 $(A_r, -r)$ 升序排列；落在该块内的询问，取其块内 0-indexed 位置 $pos$ ，直接查第 $pos+1$ 小即可得到 $(A_r, -r)$ ，从而 $r$ 也随之确定（相等的 $A_r$ 中 $r$ 大的在前，正是 $-r$ 小的在前）。
等于 $A$ 的一段：预处理任意一对 $A_l = A_r$ 。
大于 $A$ 的一段：从右到左扫描 $l$ ，数据结构维护所有 $j > l$ 的 $(A_j, j)$ 。固定 $l$ 时 $A_j > A_l$ 的那些 $j$ 是该块的候选，按 $(A_r, r)$ 升序排列；注意需要跳过值不超过 $A_l$ 的元素（它们在排名序列的最前面），即取第 $(le + pos)$ 小，其中 $le$ 是值 $\le A_l$ 的元素个数。

总复杂度 $O((N+Q)\log N + Q\log Q)$ 。

参考代码

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

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n = 0) : n(n), bit(n + 1, 0) {}
    void add(int i, int v) {                    // i: 1-indexed
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    int sum(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    int kth(int k) const {                      // 最小的 i 使得前缀和 >= k (k >= 1)
        int idx = 0, step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (; step; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int &x : A) cin >> x;

    vector<pair<ll, int>> qs;                   // (k-1, 查询编号)，按 k 升序处理
    for (int i = 0; i < Q; ++i) {
        ll k;
        cin >> k;
        qs.push_back({k - 1, i});
    }
    sort(qs.begin(), qs.end());

    // cntVal[v] = v 的个数，posLt[v] = 值小于 v 的元素总个数
    vector<int> cntVal(N + 1, 0);
    for (int x : A) cntVal[x]++;
    vector<int> posLt(N + 1, 0);
    for (int v = 1; v <= N; ++v) posLt[v] = posLt[v - 1] + cntVal[v - 1];

    ll D = 0, E = 0;
    {   // 逆序对个数 = D
        BIT fw(N);
        for (int i = 0; i < N; ++i) {
            D += i - fw.sum(A[i]);
            fw.add(A[i], 1);
        }
    }
    for (int v = 1; v <= N; ++v) E += 1LL * cntVal[v] * (cntVal[v] - 1) / 2;
    ll DE = D + E;

    vector<pair<int, int>> ans(Q);
    pair<int, int> eqPair = {-1, -1};
    {   // 相等段：任意一对 A_l == A_r (l < r)
        vector<int> last(N + 1, -1);
        for (int i = 0; i < N; ++i) {
            if (last[A[i]] != -1) eqPair = {last[A[i]], i};
            last[A[i]] = i;
        }
    }

    // 两套坐标压缩：(A_j, -j) 用于"小于 A"段，(A_j, j) 用于"大于 A"段
    vector<pair<int, int>> pd, pu;
    for (int j = 0; j < N; ++j) pd.push_back({A[j], -j});
    for (int j = 0; j < N; ++j) pu.push_back({A[j], j});
    sort(pd.begin(), pd.end());
    sort(pu.begin(), pu.end());
    vector<int> rkD(N), rkU(N);
    for (int r = 0; r < N; ++r) rkD[-pd[r].second] = r + 1;   // 1-indexed
    for (int r = 0; r < N; ++r) rkU[pu[r].second] = r + 1;

    int ptr = 0;

    // ---------- 小于 A 的一段（位置 k-1 ∈ [0, D)） ----------
    {
        BIT fw(N);
        for (int j = 0; j < N; ++j) fw.add(rkD[j], 1);
        ll cnt = 0;
        for (int l = 0; l < N; ++l) {
            fw.add(rkD[l], -1);                 // 只保留 j > l
            int lim = fw.sum(posLt[A[l]]);      // j>l 且 A_j < A_l 的个数
            while (ptr < Q && qs[ptr].first < cnt + lim) {
                int pos = (int)(qs[ptr].first - cnt);       // 块内 0-indexed
                int r = -pd[fw.kth(pos + 1) - 1].second;
                ans[qs[ptr].second] = {l + 1, r + 1};
                ++ptr;
            }
            cnt += lim;
        }
    }

    // ---------- 等于 A 的一段（位置 k-1 ∈ [D, DE)） ----------
    while (ptr < Q && qs[ptr].first < DE) {
        ans[qs[ptr].second] = {eqPair.first + 1, eqPair.second + 1};
        ++ptr;
    }

    // ---------- 大于 A 的一段（位置 k-1 ∈ [DE, M)） ----------
    {
        BIT fw(N);
        ll cnt = 0;
        for (int l = N - 1; l >= 0; --l) {
            int le = fw.sum(posLt[A[l]] + cntVal[A[l]]);    // j>l 且 A_j <= A_l 的个数
            int lim = fw.sum(N) - le;                       // j>l 且 A_j > A_l 的个数
            while (ptr < Q && qs[ptr].first < DE + cnt + lim) {
                int pos = (int)(qs[ptr].first - DE - cnt);  // 块内 0-indexed
                int r = pu[fw.kth(le + pos + 1) - 1].second; // 跳过值 <= A_l 的前缀
                ans[qs[ptr].second] = {l + 1, r + 1};
                ++ptr;
            }
            cnt += lim;
            fw.add(rkU[l], 1);                  // 为更小的 l 准备
        }
    }

    for (auto &[l, r] : ans) cout << l << ' ' << r << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O((N + Q)\log N + Q\log Q)$
空间复杂度： $O(N + Q)$