Keen On Everything But Triangle——主席树

传送门HDU6601

描述

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.

输入

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.

输出

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

样例

  • Input
    5 3
    2 5 6 5 2
    1 3
    2 4
    2 5
  • Output
    13
    16
    16

题解

  • 题意:给长度为n的数组,m组询问,每次询问给出一个区间,用区间中的三个数组成三角形,求最大周长。
  • 在每个区间中,从第1,2,3大开始组合,当无法组成三角形时,放弃第1条边找第2,3,4大的边,直到能组成三角形。
  • 证明:若第1,2,3大的三边a,b,c无法组成三角形,说明b+c<=a,那么后面任意两个数的和都不会大于a,所以只能放弃a。根据斐波那契数列和1e9的数据,在一个区间中,就算一直找不到符合条件的三条边,我们要寻找的次数不会超过50次。
  • 主席树找区间第k大。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    #include<bits/stdc++.h>
    #define INIT(a,b) memset(a,b,sizeof(a))
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define repd(i,a,b) for(int i=a;i>=b;--i)
    #define S(d) scanf("%d",&d)
    #define SLL(d) scanf("%lld",&d)
    #define P(d) printf("%d\n",d)
    #define PLL(d) printf("%lld\n",d)
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N=1e5+7;
    const int M=2e6+7;
    const int mod=998244353;
    ll a[N],b[N];
    int L[N*20],R[N*20],num[N*20],root[N];
    int tot=0,m;
    int build(int l,int r){
    int now=++tot;
    if(l<r){
    int mid=l+r>>1;
    L[now]=build(l,mid);
    R[now]=build(mid+1,r);
    }
    return now;
    }
    int update(int pre,int l,int r,int x){
    int now=++tot;
    L[now]=L[pre],R[now]=R[pre],num[now]=num[pre]+1;
    if(l<r){
    int mid=l+r>>1;
    if(x<=mid) L[now]=update(L[pre],l,mid,x);
    else R[now]=update(R[pre],mid+1,r,x);
    }
    return now;
    }
    int query(int u,int v,int l,int r,int k){
    if(l==r) return l;
    int x=num[L[v]]-num[L[u]];
    int mid=l+r>>1;
    if(x>=k) return query(L[u],L[v],l,mid,k);
    else return query(R[u],R[v],mid+1,r,k-x);
    }
    bool check(int x,int y,int z){
    if(x+y<=z||x+z<=y||y+z<=x) return false;
    return true;
    }
    ll solve(int l,int r){
    int len=r-l+1;ll e[3];
    if(len<=2)return -1;
    int k=len;
    rep(i,0,2) e[i]=b[query(root[l-1],root[r],1,m,k--)];
    while(len-k<50 && k>=0){
    if(check(e[0],e[1],e[2]))
    return e[0]+e[1]+e[2];
    e[0]=e[1];
    e[1]=e[2];
    e[2]=b[query(root[l-1],root[r],1,m,k--)];
    }
    return -1;
    }
    int main(){
    int n,q,tem;
    while(~scanf("%d%d",&n,&q)){
    tot=0;
    rep(i,1,n) {
    SLL(a[i]);
    b[i]=a[i];
    }
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    root[0]=build(1,m);
    rep(i,1,n){
    tem=lower_bound(b+1,b+1+m,a[i])-b;
    root[i]=update(root[i-1],1,m,tem);
    }
    int l,r;
    while(q--){
    S(l),S(r);
    PLL(solve(l,r));
    }
    }
    return 0;
    }
Donate comment here