题解：CF1991F Triangle Formation
William2022
·
·
题解
题目大意
给你 n 个数字 a_1,a_2,\ldots,a_n。
有 q 个问询，每次询问区间 [l,r]，询问将区间内的数字作为边长能否构建出两个非退化三角形（不能重复使用一个数字）。
# 入手
先简化问题，如果只要一个三角形，并且只有一次问询 $[1,n]$，怎么做。
直接排序，然后对所有相邻的三个数字检查是否满足 $a_i+a_{i+1} > a_{i+2}$ 即可。
如果再算几组样例，就会发现一个特殊性质：**当 $n$ 足够大时，总能找出一个三角形**。
尝试构造最长无三角形的序列，需要满足排序后 $a_i+a_{i+1} \ngtr a_{i+2}$ 并且数字最小，不难想到是 $a_i+a_{i+1} = a_{i+2}$，也就是等差数列。
而 $a_i\leq10^9$，就导致 $n$ 大概最大在 $\log_{\phi} 10^9$ 左右，使用程序验证可得 $n < 45$。
因此，当 $n \geq 45$ 时，一定存在一个三角形。
稍微推导可得，当 $n \geq 48$ 时，一定存在两个三角形。
# 解法
分类讨论，若 $r-l+1\geq48$ 直接返回 `Yes`。
否则就代表区间长度非常小，这就比较简单了，可以先取出区间内的元素并排序。
如果三个数要组成三角形，那么它们在排序后一定相邻，但两个三角形有个特殊情况就是两个三角形的六个数相邻，但一个三角形的三个数不相邻，需要特判。
先判断是否有两组不重叠的 $a_i,a_{i+1},a_{i+2}$ 能组成三角形。
再判断所有相邻的 $6$ 个数 $a_i,a_{i+1},a_{i+2},a_{i+3},a_{i+4},a_{i+5}$ 是否能组成两个三角形。
判断这两种情况就够了。
时间复杂度 $O(n+q \cdot \log A \cdot \log\log A)$，其中 $A$ 为 $a_i$ 的值域大小。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,C=50;
bool tri(int a,int b,int c){return a+b>c;}//判断有序的三个数能否组成三角形
bool check(int a,int b,int c,int d,int e,int f){//判断有序的六个数能否组成两个三角形
if(tri(a,b,c) && tri(d,e,f))return 1;
if(tri(a,b,d) && tri(c,e,f))return 1;
if(tri(a,b,e) && tri(c,d,f))return 1;
if(tri(a,b,f) && tri(c,d,e))return 1;
if(tri(a,c,d) && tri(b,e,f))return 1;
if(tri(a,c,e) && tri(b,d,f))return 1;
if(tri(a,c,f) && tri(b,d,e))return 1;
if(tri(a,d,e) && tri(b,c,f))return 1;
if(tri(a,d,f) && tri(b,c,e))return 1;
if(tri(a,e,f) && tri(b,c,d))return 1;
return 0;
}
int n,Q,a[N];
bool quest(int l,int r){//一次询问，返回布尔类型，1是yes，0是no
if(r-l+1>=C)return 1;
vector<int> v;
for(int i=l;i<=r;i++)v.emplace_back(a[i]);
sort(v.begin(),v.end());//排序
bool flg=0;
for(int i=0;i+2<v.size();i++){
if(tri(v[i],v[i+1],v[i+2])){//两组 "相邻的三个"
if(flg)return 1;
flg=1;
i+=2;
}
}
for(int i=0;i+5<v.size();i++){//特殊情况，相邻的六个
if(check(v[i],v[i+1],v[i+2],v[i+3],v[i+4],v[i+5]))return 1;
}
return 0;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>Q;
for(int i=1;i<=n;i++)cin>>a[i];
while(Q --> 0){
int l,r; cin>>l>>r;
cout<<(quest(l,r)?"Yes":"No")<<"\n";
}
}
```