题意

给你n个数，然后询问l,r区间能构成三角形的最大周长是多少？

链接

[]

分析

因为a<=1e9所以不超过44个斐波那契数，无论什么区间最多在那个范围内判断即可

也就是你要找某个区间的前四十五大的数，这个就用到主席树去找了

我有个垃圾错误浪费了我好多时间

代码

#include
    
     using namespace std;typedef long long ll;const int N = 5000000;int ls[N],rs[N],sum[N],T[N],a[N],b[N];int n,tot;void build(int l,int r,int &x){    x = ++tot;    sum[x] = 0;    if(l==r) return;    int m = (l+r)>>1;    build(l,m,ls[x]);    build(m+1,r,rs[x]);}void update(int last,int p,int l,int r,int &x){    x = ++tot;    ls[x] = ls[last];    rs[x] = rs[last];    sum[x] = sum[last] + 1;    if(l==r) return;    int m = (l+r)>>1;    if(p<=m) update(ls[last],p,l,m,ls[x]);    else update(rs[last],p,m+1,r,rs[x]);}int query(int s,int t,int l,int r,int k){    if(l==r) return l;    int m = (l+r)>>1;    int cnt = sum[ls[t]] - sum[ls[s]];    if(k<=cnt) return query(ls[s],ls[t],l,m,k);    else return query(rs[s],rs[t],m+1,r,k-cnt);}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        tot=0;        for(int i = 1;i <= n;i++)        {           scanf("%d",&a[i]);           b[i]=a[i];        }        sort(a+1,a+n+1);        int sz = unique(a+1,a+n+1) - (a+1);        build(1,sz,T[0]);        for(int i = 1; i <= n;i++) b[i] = lower_bound(a+1,a+sz+1,b[i]) - a;                for(int i = 1;i <= n;i++) update(T[i-1],b[i],1,sz,T[i]);                int x,y,k;        while(m--)        {            scanf("%d%d",&x,&y);            ll ans = -1;            k=(y-x+1);            bool flag = 0;            for(int i = k;i >= 3;i--){                int x1 = query(T[x-1],T[y],1,sz,i);                int x2 = query(T[x-1],T[y],1,sz,i-1);                int x3 = query(T[x-1],T[y],1,sz,i-2);                if(1ll*a[x2]+1ll*a[x3] > 1ll*a[x1]){                    ans = 1ll*a[x1]+a[x2]+a[x3];//我错的是没把后面转成long long 就死在那里                    flag=1;                    break;                }            }            if(flag)            printf("%lld\n",ans);            else puts("-1");        }   }    return 0;}