题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6601

题目大意：
给你一个长度为nn的序列，有q个询问，每个询问给你一个区间[l,r]，每次询问问你在区间[l,r]中，能够组成的最大的三角形的周长。

思路：
因为三角形具有两边之和大于第三边的性质，即a+b>c的性质。而倘若有若干个数都符合条件，则倘若我们将不等号改成等号，这就形成了一个斐波那契数列。而根据斐波那契数列的性质，值域在[1,a]的斐波那契数列最多会有log2(a)项。
而在这里可以利用这个性质，每个询问我们贪心的去取第k大、第k+1大、第k+3大的数进行比较，如果不符合条件则继续向后找第k+4项直到找到答案为止。因为值域上限为10^9故最大只需要枚举大概44。而每次寻找第k大，我们可以用主席树在O(logn)的时间复杂度下进行查询第kk大。故整体的时间复杂度为：O(44qlogn)

#include<bits/stdc++.h>

#define LL long long
using namespace std;
const int maxn=2e5+10;

LL L[maxn*20], R[maxn*20], sum[maxn*20];
LL n, q, m ,cnt = 0;
LL a[maxn], b[maxn], root[maxn];

#define mid (l+r)/2
LL JS(LL l, LL r)
{
    LL rt=++cnt;
    sum[rt]=0;
    if(l<r)
    {
        L[rt]=JS(l ,mid);
        R[rt]=JS(mid+1, r);
    }
    return rt;
}

LL gx(LL i, LL l, LL r, LL x)
{
    LL rt=++cnt;
    L[rt]=L[i], R[rt]=R[i], sum[rt]=sum[i]+1;//更新
    if(l<r)
    {
        if(x<=mid)
        {
            L[rt]=gx(L[i], l, mid, x);
        }
        else
        {
            R[rt]=gx(R[i], mid+1, r, x);
        }
    }
    return rt;
}

LL cx(LL u, LL v, LL l, LL r, LL k)
{
    if(l>=r)
    {
        return l;                        //找到区间
    }
    LL x=sum[L[v]]-sum[L[u]];
    if(x>=k)
    {
        return cx(L[u], L[v], l, mid, k);//递归查找
    }
    else
    {
        return cx(R[u], R[v], mid+1, r, k-x);//放4递归查找
    }
}

LL LSH()                               //离散化
{
    sort(b+1, b+1+n);
    m = unique(b+1, b+1+n)-b-1;
    for (LL i = 1; i <= n; i ++)
    {
        a[i] = lower_bound(b+1, b+1+m, a[i])-b;
    }
}

int main()
{
    while(~scanf("%lld%lld", &n, &q))
    {
        cnt = 0;
        for (LL i = 1; i <= n; i ++)
        {
            scanf("%lld", &a[i]);
            b[i] = a[i];
        }
        LSH();

        root[0] = JS(1, cnt);

        for(LL i=1;i<=n;i++)
        {
            root[i]=gx(root[i-1], 1, m, a[i]);//更新
        }

        while (q --)
        {
            LL x, y, z, f=0;
            scanf("%lld%lld", &x, &y);

            if(y-x+1<3)
            {
                printf("-1\n");
                continue;
            }

            LL a=b[cx(root[x-1], root[y], 1, m, (y-x+1))];
            LL c=b[cx(root[x-1], root[y], 1, m, (y-x))];

            for(LL Len=(y-x-1); Len>=1; Len--)
            {
                LL d=b[cx(root[x-1], root[y], 1, m, Len)];

                if((c+d)>a)
                {
                    printf("%lld\n", a+d+c);
                    f=1;
                    break;
                }
                else
                {
                    a=c;
                    c=d;
                }
            }
            if(!f)
            printf("-1\n");
        }
    }

    return 0;
}