hdu6601 主席树

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

Problem Description

N sticks are arranged in a row, and their lengths are a1,a2,...,aN.

There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.

Input

There are multiple test cases.

Each case starts with a line containing two positive integers N,Q(N,Q≤105).

The second line contains N integers, the i-th integer ai(1≤ai≤109) of them showing the length of the i-th stick.

Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.

It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×105.

Output

For each test case, output Q lines, each containing an integer denoting the maximum circumference.

Sample Input

5 3

2 5 6 5 2

1 3

2 4

2 5

Sample Output

主席树求最大三条边，如果三边能组成三角形即为答案，否则再找第二大第三大第四大的边，一直找到符合的

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 100005

#define ll long long

int T[maxn*],L[maxn*],R[maxn*],sum[maxn*],tot;

ll a[maxn],b[maxn];

inline int update(int pre,int l,int r,int x)

{

    int rt=++tot;

    L[rt]=L[pre];

    R[rt]=R[pre];

    sum[rt]=sum[pre]+;

    if(l<r)

    {

        int mid=l+r>>;

        if(x<=mid)L[rt]=update(L[pre],l,mid,x);

        else R[rt]=update(R[pre],mid+,r,x);

    }

    return rt;

}

inline int query(int u,int v,int l,int r,int k)

{

    if(l>=r)return l;

    int x=sum[L[v]]-sum[L[u]],mid=l+r>>;

    if(x>=k)return query(L[u],L[v],l,mid,k);

    else return query(R[u],R[v],mid+,r,k-x);

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=;i<=n;i++)

        {

            scanf("%lld",&a[i]);

            b[i]=a[i];

        }

        sort(b+,b++n);

        int len=unique(b+,b++n)-b-;

        T[]=L[]=R[]=sum[]=tot=;

        for(int i=;i<=n;i++)

        {

            int pos=lower_bound(b+,b++len,a[i])-b;

            T[i]=update(T[i-],,len,pos);

        }

        for(int i=;i<=m;i++)

        {

            int l,r;

            int flag=;

            ll ans=;

            scanf("%d%d",&l,&r);

            for(int i=r-l+;i>=;i--)

            {

                ll A=b[query(T[l - ],T[r],,len,i)];

                ll B=b[query(T[l - ],T[r],,len,i-)];

                ll C=b[query(T[l - ],T[r],,len,i-)];

                if(B+C>A)

                {

                    flag=;

                    ans=A+B+C;

                    break;

                }

            }

            if(flag)printf("%lld\n",ans);

            else printf("-1\n");

        }

    }

    return ;

}

巴特西

hdu6601 主席树

最新文章

热门文章