题意简述

给定数组 $a_1 \dots a_n$，$q$ 次询问区间 $[l, r]$，能否从该区间内选出 6 根不同棍子组成 2 个非退化三角形。$n, q \le 10^5$，$r-l+1 \ge 6$。

关键性质

• 三角形条件：三边长 $x \le y \le z$ 满足 $x + y > z$。
• 斐波那契数列的性质：若一序列中的任意三个数都不能构成三角形，则该序列的增长速度至少与斐波那契数列一样快（每个数不小于前两个数之和）。由于 $a_i \le 10^9$，这样的序列长度最多约 $45$。因此，任意长度 $> 45$ 的区间内必存在至少一个三角形。
• 对于两个不相交的三角形，当区间长度 $> 60$ 时，必然存在两个三角形（可取出两个互不重叠的“斐波那契块”）。实际阈值可取 $60$。

解法

1. 预处理：无。
2. 对于每个询问 $[l, r]$：
   • 若区间长度 $len > 60$，直接输出 YES。
   • 否则，将 $a_l \dots a_r$ 复制到临时数组，排序。
   • 暴力枚举第一个三角形的三条边（索引 $i < j < k$），判断是否满足 $a_i + a_j > a_k$。
     • 若满足，标记这三个位置已使用，然后在剩余的边中贪心地寻找第二个三角形：扫描未被使用的元素，检查连续三个是否满足三角形条件。
     • 若两个三角形都找到，输出 YES，进入下一询问。
   • 若所有枚举都失败，输出 NO。

复杂度分析

• 对于 $len \le 60$ 的询问，枚举三角形 $O(len^3)$ 再贪心扫描 $O(len)$，单次约 $2 \times 10^6$ 次操作。
• 由于 $len > 60$ 的询问直接返回，实际需要暴力的询问极少，总复杂度可接受。

细节

• 阈值可设为 $60$，足够安全。
• 可以使用 vector<int> 存子区间，排序后 vector<bool> used 标记已被第一个三角形占用的位置。

参考代码

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

bool has_triangle(const vector<int>& a, vector<bool>& used) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        for (int j = i + 1; j < n; ++j) {
            if (used[j]) continue;
            for (int k = j + 1; k < n; ++k) {
                if (used[k]) continue;
                if (a[i] + a[j] > a[k]) return true;
            }
        }
    }
    return false;
}

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

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    const int THRESHOLD = 60; // 长度阈值

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        int len = r - l + 1;
        if (len > THRESHOLD) {
            cout << "YES\n";
            continue;
        }

        // 提取区间并排序
        vector<int> seg(a.begin() + l, a.begin() + r + 1);
        sort(seg.begin(), seg.end());

        bool ok = false;
        int m = seg.size();
        // 枚举第一个三角形的三条边
        for (int i = 0; i < m && !ok; ++i) {
            for (int j = i + 1; j < m && !ok; ++j) {
                for (int k = j + 1; k < m && !ok; ++k) {
                    if (seg[i] + seg[j] > seg[k]) {
                        vector<bool> used(m, false);
                        used[i] = used[j] = used[k] = true;
                        // 检查剩余部分是否有三角形
                        if (has_triangle(seg, used)) {
                            ok = true;
                        }
                    }
                }
            }
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}