题目链接：https://ac.nowcoder.com/acm/contest/11180/D

思路：我们先考虑最大的集合中多少个数是不能组成三角形的
假如这个集合是排过序的
不能组成三角形意味着a[i-1]+a[i-2]>=a[i] (i>=2)
同时我们要这个集合中包含的元素尽可能多，又因为上限1e9是确定的
那么我们就可以让第一个第二个元素为1即a[1]=1,a[2]=1
之后的元素都为a[i]=a[i-1]+a[i-2]
那么可以发现这东西就是斐波那契数列
并且通过模拟会发现集合最多44个元素
那么如果集合中有45个及以上的元素的话那就肯定有任意三个数能组成三角形
这样的话那么我们就是对集合中45个以上的元素的集合不进行加的操作并且查询时直接输出YES就好了
这里的操作有很多方法，有线段树有树状数组做的，在这里的我是采用了并查集的做法（这个算是比较快的）
对于一个集合如果有了45个元素，那么就并入右边的点中，下次要进行操作的时候就直接跳到右边的点不经过这个点了
剩下的注意45这个数模拟操作就好

AC代码：

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+10;
const int b=45;
int fa[N];
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
vector<int>a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        fa[i]=i;
        a[i].push_back(x);
    }
    fa[n+1]=n+1;
    while(m--)
    {
        string s;
        int l,r;
        cin>>s>>l>>r;
        if(s[0]=='A')
        {
            if(r-l+1>=b)
            {
                puts("YES");
                continue;
            }
            int ok=0;
            vector<int>temp;
            for(int i=l; i<=r; i++)
            {
                if(a[i].size()>=b||temp.size()>=b)
                {
                    ok=1;
                    break;
                }
                for(int j=0; j<a[i].size(); j++)temp.push_back(a[i][j]);
            }
            sort(temp.begin(),temp.end());
            for(int i=0; i+2<temp.size(); i++)//注意这里不能写成i<temp.size()-2 因为temp.size()是ull类型的不能为负
            {
                if(temp[i]+temp[i+1]>temp[i+2])
                {
                    ok=1;
                    break;
                }
            }
            if(ok)puts("YES");
            else puts("NO");
        }
        else
        {
            int x;
            cin>>x;
            for(int i=findfa(l); i<=r; i=findfa(i+1))//往右边跳
            {
                a[i].push_back(x);
                if(a[i].size()>=b)fa[i]=findfa(i+1);//连向右边所在的并查集
            }
        }
    }
    return 0;
}