牛客练习赛90 D.妄想集合 线段树+Set+数学

题目思路：首先需要理解一个规律：

根据三角形定义，若 a , b , c a,b,c a,b,c构成三角形,则 a + b > a+b> a+b>c且 ∣ a − b ∣ |a-b| ∣a−b∣不为 0 0 0，很容易发现：当数列中的所有数都是斐波那契数列中的数的时候，任意三个数不能组成三角形。

那么我们对斐波那契数列进行研究，可以发现到第 45 45 45项之后数值已经非常大，超过了题目可能出现的数据范围。因此对于不可重集合中元素数量大于 45 45 45的情况，对于本体的数据范围一定存在三角形。

那么我们用一棵线段树维护区间集和元素总个数，用一个类似邻接表的结构储存每个叶节点中的集合。每次首先查询区间内的元素总数目。如果数目大于 45 45 45，那么区间一定有解。对于小于等于 45 45 45的情况，直接区间暴力二分查找，检索满足题意的情况。

#include 
#define ll long long
using namespace std;

const int N = 1e6;
int d[N][70], cnt[N];

set S;

int n, m, tree[N