CF1991F Triangle Formation 题解

Description

你有 $n$ 根棍子，从 $1$ 到 $n$ 编号。第 $i$ 根棍子的长度是 $a_i$。

你需要回答 $q$ 个问题。在每个查询中，你会得到两个整数 $l$ 和 $r$（$1 \le l < r \le n，r − l + 1 \ge 6$）。确定是否可以从编号为 $l$ 到 $r$ 的棒中选择 $6$ 个不同的棒，形成 $2$ 个非退化三角形。

边长为 $a$、$b$ 和 $c$ 的三角形称为非退化三角形，当且仅当 $a<b+c,b<a+c,c<a+b$。

Solution

先考虑什么样的序列存在至少一个三角形。容易发现把序列排序后，如果存在三角形，则必存在一个长度为 $3$ 的连续区间满足条件。

而如果不存在，则一定满足 $a_i\geq a_{i-1}+a_{i-2}$。经过计算，这样的序列长度一定不超过 $45$，即长度不小于 $45$ 的序列一定存在至少一个三角形。

回到这个题。利用上面那个结论可以得出序列长度 $\geq 48$ 时一定存在答案，因为这里至少存在一个三角形，去掉这个三角形后还剩 $45$ 个数，所以存在第二个。

于是 $r-l+1\geq 48$ 时必然有解，现在需要判断 $r-l+1\leq 47$ 时是否有解。

同样是先排序，把所有形如 $(i,i+1,i+2)$ 且满足 $a_i+a_{i+1}>a_{i+2}$ 的数对拿出来，如果存在两个数对不相交则一定有解。

如果不存在则说明最终的两个三角形是相交的，就像 $(1,2,4),(3,5,6)$ 这种。注意到这时选的 $6$ 个数如果不是连续的 $6$ 个则调整成连续的一定更优，所以只需要对于所有连续的 $6$ 个数暴力判断即可。

时间复杂度：$O(n\log V\log\log V)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n, q;
int a[kMaxN];

bool check(int64_t x, int64_t y, int64_t z) {
  return x + y > z && x + z > y && y + z > x;
}

bool check(int l, int r) {
  std::vector<int> vec;
  for (int i = l; i <= r; ++i) vec.emplace_back(a[i]);
  std::sort(vec.begin(), vec.end());
  int mi = 1e9;
  for (int i = 2; i < (int)vec.size(); ++i) {
    if (check(vec[i - 2], vec[i - 1], vec[i])) {
      if (i - 2 > mi) return 1;
      if (mi == 1e9) mi = i;
    }
  }
  for (int i = 0; i + 5 < (int)vec.size(); ++i) {
    if (check(vec[i], vec[i + 1], vec[i + 2]) && check(vec[i + 3], vec[i + 4], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 1], vec[i + 3]) && check(vec[i + 2], vec[i + 4], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 1], vec[i + 4]) && check(vec[i + 2], vec[i + 3], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 1], vec[i + 5]) && check(vec[i + 2], vec[i + 3], vec[i + 4])) return 1;
    if (check(vec[i], vec[i + 2], vec[i + 3]) && check(vec[i + 1], vec[i + 4], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 2], vec[i + 4]) && check(vec[i + 1], vec[i + 3], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 2], vec[i + 5]) && check(vec[i + 1], vec[i + 3], vec[i + 4])) return 1;
    if (check(vec[i], vec[i + 3], vec[i + 4]) && check(vec[i + 1], vec[i + 2], vec[i + 5])) return 1;
    if (check(vec[i], vec[i + 3], vec[i + 5]) && check(vec[i + 1], vec[i + 2], vec[i + 4])) return 1;
    if (check(vec[i], vec[i + 4], vec[i + 5]) && check(vec[i + 1], vec[i + 2], vec[i + 3])) return 1;
  }
  return 0;
}

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i <= q; ++i) {
    int l, r;
    std::cin >> l >> r;
    if (r - l + 1 >= 48) std::cout << "YES\n";
    else std::cout << (check(l, r) ? "YES\n" : "NO\n");
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}