考虑三个树枝:a,b,c

若c是将要抛出的树枝,那么形成三角形的条件是

a+b>c and a-b<c 可以写成 c属于开区间(a-b,a+b)

对于每个C和许许多多的其他边，如何保证C不构成三角形?

可以看到：对于每个a,要使得这个(a-b,a+b)尽可能的大,就要让b在小于a的基础上尽可能地大

那么我们可以排序等到n-1个这样的区间。只要C不在这些区间内,就一定不会构成三角形。

那么问题转化为区间问题了。

我们把包含在(L,R)区间且不与以上的所有区间相交的部分累加起来就得到了结果

首先离散化,-1代表进区间,1代表出区间

1.当上一个区间已经出来而进入下一个区间时,两个区间中间的部分可以积累

2.L到第一个区间的左边界可以积累

3.最后一个区间的有边界到R可以积累

#include 
      
       #define MP(x,y) make_pair(x,y)using namespace std;typedef long long LL;const int Max=1e5+10;LL A[Max];pair
       
         B[Max*2];int main(){    int T;    for(scanf("%d",&T);T;T--)    {        int n;        LL L,R;        scanf("%d%I64d%I64d",&n,&L,&R);        for(int i=0;i
        
         =0) ans+=dis;            }            count+=B[i].second;            pre=B[i].first;        }        disr=R;disl=max(L,pre);        dis=disr-disl+1;        if(dis>=0) ans+=dis;        printf("%I64d\n",ans);    }    return 0;}