原题链接

tags: 思维，数学，*2200

题意

给你一个长度为 的序列 ，进行 次询问，每次询问给出 ，询问区间 中能否选出 个数组成两个非退化的三角形。

非退化三角形：边长分别为 ，则有：

题解

一开始以为会是一道数据结构大题……

但是很容易发现，如果一个区间中不包含两个退化的三角形，则一定有任意三个数都不满足上面三个条件，更具体的，任意选三个数，最小的两个数相加一定小于等于最大的那个数。

那么将区间中所有的数按照递增排序，则有 ，这使我们联系到斐波那契数列，由于斐波那契数列增长速度相当快，打表发现满足小于 ​ 的只有前 44 项。

1
2
3
4
5
6
vector<long long> a = {1, 1};
while (a.back() <= 1e9) {
    a.push_back(a[a.size() - 1] + a[a.size() - 2]);
}
cout << a.size() << endl;  // 45
cout << a.back() << endl;  // 1134903170

因此当区间长度大于 44 是就一定存在一个非退化的三角形，如果再往区间中扔 3 个数，则一定存在两个非退化的三角形，因此只要区间长度大于47，则一定存在两个非退化的三角形，下面考虑计算长度小于等于 47 的区间。

首先还是先将区间中所有数拿出来排序（因为现在个数很少，直接暴力验证）。有两个性质需要说明：

  • 对于已经能够形成三角形的 3 个数，在保证仍然是最小的条件下将最小的边拉长将不会影响合法性。
  • 对于已经能够形成三角形的 3 个数，在保证仍然是最大的条件下将最大的边拉短将不会影响合法性。

有了这两条性质，我们能够得到，在排好序的序列中，选择相邻的三个合法的一定更优，若不存在三个相邻的数能够组成非退化三角形则整个序列中都不会存在。

因此，我们只需要扫一遍排好序的序列，判断是否有不相交的两组相邻三个数能够组成非退化三角形，如果存在打印“YES”。

上面只考虑了两组数不相交的情况，但是有可能存在两组数相交的特例。例如： ，如果选择两组相邻的，即 和 ，前面第一组就不合法，如果按照 和 ​ 进行划分就存在合法解。因此我们还需要扫一遍相邻 6 个数判断是否存在两组合法解。

时间复杂度：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

constexpr int d[9][6] = {
    {1, 2, 4, 3, 5, 6}, {1, 2, 5, 3, 4, 6}, {1, 2, 6, 3, 4, 5}, {1, 3, 4, 2, 5, 6}, {1, 3, 5, 2, 4, 6}, {1, 3, 6, 2, 4, 5}, {1, 4, 5, 2, 3, 6}, {1, 4, 6, 2, 3, 5}, {1, 5, 6, 2, 3, 4}};

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    while (q--) {
        int l, r;
        cin >> l >> r;
        if (r - l + 1 >= 48) {
            cout << "YES" << endl;
            continue;
        }
        vector<int> nums;
        for (int i = l; i <= r; i++) {
            nums.push_back(a[i]);
        }
        sort(nums.begin(), nums.end());

        auto check = [&](int a, int b, int c) { return a < (b + c) && b < (a + c) && c < (a + b); };

        vector<int> ok;
        bool have = false;

        for (int i = 0; i < nums.size() - 2; i++) {
            if (check(nums[i], nums[i + 1], nums[i + 2])) {
                ok.push_back(i);
                if (ok.back() > ok[0] + 2) {
                    have = true;
                    break;
                }
            }
        }

        if (ok.empty()) {  // 不存在合法三角形
            cout << "NO" << endl;
            continue;
        }

        if (have) {  // 存在不相交的两组数
            cout << "YES" << endl;
            continue;
        }

        for (int i = 0; i < nums.size() - 5; i++) {
            for (int j = 0; j < 9; j++) {
                if (check(nums[i + d[j][0] - 1], nums[i + d[j][1] - 1], nums[i + d[j][2] - 1]) && check(nums[i + d[j][3] - 1], nums[i + d[j][4] - 1], nums[i + d[j][5] - 1])) {
                    have = true;
                    break;
                }
            }
            if (have) break;
        }

        if (have) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。