题目大意

现在有n个集合，让你完成以下操作

1. 往l~r的集合中加入一个数x
2. 查询l~r的集合内的数是否能构成三角形

解题思路

如果一个集合内构不成三角形，那么要使里面的数最多，集合就形如1,1,2,3,5,8...

不难发现这是个斐波那契数列，可以推出45位以后就大于$10^{9}10^9$了，所以一个集合只用维护45个数

对于每次查询，只加45个数即可

时间复杂度$O(45\times n)O(45\backslash times\; n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
int n,m,x,y,z,now,pp,s[N],fa[N],a[N][100];
char c[N];
int find(int x)
{
	return (x==fa[x]?x:fa[x]=find(fa[x]));
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i][++a[i][0]]);
		fa[i]=i;
	}
	fa[n+1]=n+1;
	while(m--){
		scanf("%s",c+1);
		if(c[1]=='Q'){
			scanf("%d%d%d",&x,&y,&z);
			x=find(x);
			while(x<=y){
				x=find(x);
				a[x][++a[x][0]]=z;
				if(a[x][0]==45)fa[x]=fa[x+1];
				x++;
			}
		}
		else{
			scanf("%d%d",&x,&y);
			now=0;
			for(int i=x;i<=y;++i){
				for(int j=1;j<=a[i][0];++j){
					s[++now]=a[i][j];
					if(now==45)break;
				}
				if(now==45)break;
			}
			sort(s+1,s+1+now);
			pp=0;
			for(int i=1;i<=now-2;++i)
				if(s[i]+s[i+1]>s[i+2]){
					pp=1;
					break;
				}
			if(pp)puts("YES");
			else puts("NO");
		}
	}
	return 0;
}