图片说明

  • 题意：
  • 给出n个木棒，每次询问区间[l,r],问你选择任意三根木棒能够构成的最大的三角形，如果不存在三角形，输出-1
  • 题解：
  • 肯定都知道三角形的三边的定理，任意俩边之和大于第三边，
  • 假设从最小的三角形都不匹配，
  • 1，2，3，5，8，13，，，，
  • 形成了斐波那契数列，第44项超过1e9，那么只需枚举前44项三角形就行了，如果还是没有符合的输出-1
  • 找第k大值可以用主席树区间查找
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 2e5+7;
int n,m,q,cnt,a[maxx],b[maxx],x,y,k;
int t[maxx*50],ls[maxx*50],rs[maxx*50],sum[maxx*50];
int build(int l,int r)
{
  int now = ++cnt;
  if(l < r)
  {
      int mid = (l+r)>>1;
      ls[now]=build(l,mid);
      rs[now]=build(mid+1,r);
  }
  return now;
}
void build_new(int mark,int loc)
{
  t[mark] = ++cnt;
  sum[cnt] = sum[t[mark-1]] +1;
  int l=1,r=m,now=cnt,still=t[mark-1];
  for(;ls[still] || rs[still];)
  {
      int mid = (l+r)>>1;
      if(loc > mid)
      {
          ls[now] = ls[still];
          rs[now] =++cnt;
          sum[rs[now]] = sum[rs[still]]+1;
          now = rs[now];
          still = rs[still];
          l = mid+1;
      }
      else
      {
          rs[now] = rs[still];
          ls[now] = ++cnt;
          sum[ls[now]] = sum[ls[still]] +1;
          now = ls[now];
          still = ls[still];
          r = mid;
      }
  }
}
int query(int a,int b,int l,int r,int k)
{
  if(l == r)
      return l;
  int lm = sum[ls[b]] - sum[ls[a]];
  int mid = (l+r)>>1;
  if(k<=lm)
      return query(ls[a],ls[b],l,mid,k);
  return query(rs[a],rs[b],mid+1,r,k-lm);
}
int main()
{
  while(~scanf("%d%d",&n,&q))
  {
      for(int i=1;i<=n;i++)
      {
          scanf("%d",&a[i]);
          b[i] = a[i];
      }
      sort(b+1,b+1+n);
      m = unique(b+1,b+1+n)-b-1;
      t[0] = build(1,m);
      for(int i=1;i<=n;i++)
      {
          int loc = lower_bound(b+1,b+1+m,a[i]) - b;
          build_new(i,loc);
      }
      for(int i=1;i<=q;i++)
      {
          scanf("%d %d",&x,&y);
          int len = y-x+1;
          int flag = 45;
          int k1 = 0,k2 = 0,k3 = 0;
          ll ans = -1;
          while(len >= 3 && flag>=0)
          {
              if(k1 && k2 && k3){
                  k1 = k2,k2 = k3;
                  k3 = b[query(t[x-1],t[y],1,m,len-2)];
              }
              else{
                  k1 = b[query(t[x-1],t[y],1,m,len)];
                  k2 = b[query(t[x-1],t[y],1,m,len-1)];
                  k3 = b[query(t[x-1],t[y],1,m,len-2)];
              }
              if((k1<k2+k3)&&(k2<k1+k3)&&(k3<k1+k2))
              {
                  ans = 1LL*k1 + 1LL*k2 + 1LL*k3;
                  break;
              }
              len--;
              flag--;
          }
          printf("%lld\n",ans);
      }
  }
  return 0;
}