一、核心结论（题眼）

原问题中： 子数组 $b$ 是完美数组（输出 $\text{YES}$） $\iff$ 子数组中不存在 $i$ 满足 $b_i > b_{i+1} > b_{i+2}$。 子数组不是完美数组（输出 $\text{NO}$） $\iff$ 子数组中存在 $i$ 满足 $b_i > b_{i+1} > b_{i+2}$。

结论推导

1. $g(b)$ = 数组的逆序对数量（仅相邻交换的最小次数）。
2. 操作2（交换隔一个位置的元素）最多用1次：
   • 若存在 $b_i > b_{i+1} > b_{i+2}$，用1次操作2能直接减少3个逆序对，让 $f(b) < g(b)$，数组不完美。
   • 若不存在这样的连续三元组，操作2无法减少逆序对，$f(b)=g(b)$，数组完美。

✅ 最终问题简化： 对每个询问 $[l,r]$，判断区间内是否存在连续递减三元组 $a[x]>a[x+1]>a[x+2]$。

• 存在 $\to$ 输出 $\text{NO}$
• 不存在 $\to$ 输出 $\text{YES}$

二、标程算法原理

标程没有暴力找三元组，而是用前驱更大元素、后继更小元素定位所有「危险三元组」，再预处理出前缀最大左边界数组，实现 $O(1)$ 查询。

1. 定义两个关键数组

• $mxl[i]$：$i$ 左侧最近的满足 $a[mxl[i]] > a[i]$ 的下标（左侧第一个比 $a[i]$ 大的数）。
• $mir[i]$：$i$ 右侧最近的满足 $a[mir[i]] < a[i]$ 的下标（右侧第一个比 $a[i]$ 小的数）。

若 $mxl[i]$ 和 $mir[i]$ 都存在，说明 $a[mxl[i]] > a[i] > a[mir[i]]$，即构成了一组递减三元组。

2. 预处理答案数组 $L$

• $L[r]$：表示以 $r$ 为右端点，所有危险三元组的最大左端点。
• 预处理后：询问 $[l,r]$ 中，若 $l \le L[r]$，说明区间包含危险三元组，输出 $\text{NO}$。

三、标程代码逐行解析

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

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 2);  // 下标从1开始，方便处理边界
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 1. 求 mxl[i]：i左侧第一个比 a[i] 大的下标
    vector<int> mxl(n + 1);
    for (int i = 1; i <= n; i++) {
        mxl[i] = i - 1;
        // 跳跃查找，类似并查集路径压缩，O(n)时间
        while (mxl[i] > 0 && a[mxl[i]] < a[i])
            mxl[i] = mxl[mxl[i]];
    }

    // 2. 求 mir[i]：i右侧第一个比 a[i] 小的下标
    vector<int> mir(n + 1);
    for (int i = n; i >= 1; i--) {
        mir[i] = i + 1;
        while (mir[i] <= n && a[mir[i]] > a[i])
            mir[i] = mir[mir[i]];
    }

    // 3. 预处理 L 数组：L[r] = 右端点为 r 的所有危险三元组的最大左端点
    vector<int> L(n + 1, 0);
    for (int i = 2; i < n; i++) {  // i必须能构成三元组（左右都有数）
        if (mxl[i] > 0 && mir[i] <= n) {
            // 三元组：mxl[i] → i → mir[i]，右端点是 mir[i]
            L[mir[i]] = max(L[mir[i]], mxl[i]);
        }
    }

    // 4. 前缀最大值，保证 L[r] 是最优答案
    for (int i = 1; i <= n; i++) {
        L[i] = max(L[i], L[i - 1]);
    }

    // 5. 处理询问，O(1) 每个查询
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l <= L[r]) cout << "NO\n";  // 包含危险三元组
        else cout << "YES\n";           // 无危险三元组，完美数组
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);  // 加速输入输出
    int T;
    cin >> T;
    while (T--) solve();
}

四、查询判定规则（最重要）

对询问 $[l, r]$：

1. 若 $l \le L[r]$： 区间内存在连续递减三元组 $\to$ $f(b) \not= g(b)$ $\to$ 输出 $\text{NO}$。
2. 若 $l > L[r]$： 区间内无任何连续递减三元组 $\to$ $f(b) = g(b)$ $\to$ 输出 $\text{YES}$。

五、时间复杂度

• 预处理 $mxl, mir$：$O(n)$（跳跃查找，均摊复杂度）。
• 预处理 $L$ 数组：$O(n)$。
• 每个询问：$O(1)$。
• 总复杂度：$O(n + q)$，完全通过 $5 \times 10^5$ 数据范围。

六、结合样例验证

样例1

数组：$[1,5,4,3,2]$ 危险三元组： $5>4>3,\ 4>3>2$

• 询问 $[1,2]$：无危险三元组 $\to \text{YES}$
• 询问 $[1,5]$：包含所有危险三元组 $\to \text{NO}$
• 询问 $[3,5]$：包含 $4>3>2$ $\to \text{NO}$

与样例输出完全一致。

总结

1. 核心转化：完美数组 $\iff$ 无连续递减三元组 $a[x]>a[x+1]>a[x+2]$。
2. 算法核心：用 $mxl, mir$ 定位所有递减三元组，预处理 $L$ 数组。
3. 查询方式：$l \le L[r] \to \text{NO}$，否则 $\text{YES}$。
4. 复杂度：线性预处理，$O(1)$ 查询，适合大数据。