题解：CF1991F Triangle Formation

· · 题解

题意：有 n 个长度 a_i。静态询问能否从区间 [l, r] 中选出 6 根凑成两个非退化三角形。

做法：若只要求凑出一个三角形，可以证明将 [l, r] 排序后，原问题等价于是否存在 i\in[l, r - 2] 满足 a_i + a_{i + 1} > a_{i+2}。证明如下：

充分性显然。

必要性。若不存在 a_i + a_{i+1} > a_{i+2}（即所有 i 都满足 a_i+a_{i+1} \le a_{i+2}），那么一定凑不出三角形。反证法。若能凑出，不妨令这三条线段分别为 i, i + x, i + x + y（x \ge 1, y \ge 1）。因为排过序，所以 a_i \le a_{i+x} \le a_{i+x+y}。因为所有 i 都满足 a_i + a_{i+1} \le a_{i+2}，所以 a_i + a_{i+x} \le a_{i+x+y-2} + a_{i+x+y-1} \le a_{i+x+y}。所以 i,i+x,i+x+y 这三条线段也不能凑出。

可以证明，当区间长度 \ge 45 时，一定有解。证明如下：

证逆否。

若无解，即对于所有 i 都满足 a_i + a_{i + 1} \le a_{i+2}。因为 a_l \ge 1, a_{l+1} \ge 1，所以 a_i \ge Fib_i。其中 Fib_i 表示斐波那契数列（Fib_1 = Fib_2 = 1, Fib_i = Fib_{i-1} + Fib_{i-2}）。因为 Fib_{45} = 1134903170 \ge 10^9 \ge a_i，所以区间长度必定 < 45。

考虑两个三角形。

可以证明，当区间长度 \ge 48 时，一定有解。证明如下：

首先一定能凑出一个三角形，因为 48 > 45。

将这个三角形的三条边去掉后，剩下的数量 \ge 48-3 = 45。又可以凑出一个。

所以对于剩下的情况暴力即可。

但是暴力也不能六次方的复杂度。我们可以考虑：

// Problem: Triangle Formation
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1991F
// Memory Limit: 250 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

int n, q, a[N], b[N];
vector<int> S;
int sum[2], mx[2];

signed main() {
    for (int i = 0; i < 1 << 6; ++ i )
        if (__builtin_popcount(i) == 3 && i != 1 + 2 + 4 && i != 8 + 16 + 32) {
            S.push_back(i);
        }

    cin >> n >> q;

    for (int i = 1; i <= n; ++ i ) cin >> a[i];

    while (q -- ) {
        int l, r;
        cin >> l >> r;
        if (r - l + 1 >= 48) puts("YES");
        else {
            int m = 0;
            for (int i = l; i <= r; ++ i ) b[ ++ m] = a[i];

            sort(b + 1, b + m + 1);

            int L = 1e9, R = -1e9;
            for (int i = 1; i + 2 <= m; ++ i )
                if (b[i] + b[i + 1] > b[i + 2]) {
                    L = min(L, i);
                    R = i;
                }

            if (L + 2 < R) puts("YES");
            else {
                bool flg = false;

                for (int i = 1; i + 5 <= m && !flg; ++ i )
                    for (int s : S) {
                        sum[0] = sum[1] = mx[0] = mx[1] = 0;

                        for (int j = 0; j < 6; ++ j ) {
                            int w = s >> j & 1;
                            sum[w] += b[i + j];
                            mx[w] = max(mx[w], b[i + j]);
                        }

                        if (mx[0] < sum[0] - mx[0] && mx[1] < sum[1] - mx[1]) {
                            flg = true;
                            break;
                        }
                    }

                puts(flg ? "YES" : "NO");
            }
        }
    }

    return 0;
}