题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6601
题意：
给你n个数字和q个询问，每次询问给你一个区间l， r 。问你在这个区间中能否找到三个数能组成三角形，如果能，请给出周长最大的三角形的周长，如果不能则输出-1。
做法：
啊啊啊想到死，真是懊恼明明离想的很近了来着。如果不能形成三角形，最坏情况下是形成了斐波那契数列，如1 1 2 3 5 ，使得a<=b<=c的时候形成了a+b=c，可斐波那契数列在第45项就已经超过了1e9，所以只要找到区间前45个大的数字就至少有三个数字可以形成三角形，假设a<=b<=c<=d，那如果a+b>d的话那b+c>d也是一定的，所以能形成最大三角形的三个数一定的连续的，然后就是主席树求区间第k大模板了。。只要for不超过50次就好了，复杂度是n*logn*50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int root[maxn],n,q;
int cnt,a[maxn];
vector<int> v;
struct node{
int lson,rson,num;
}e[maxn*40];
int gain(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void update(int l,int r,int &now,int pre,int a){
now=++cnt;
e[now]=e[pre];
e[now].num++;
if(l==r) return ;
int mid=(l+r)/2;
if(a<=mid) update(l,mid,e[now].lson,e[pre].lson,a);
else update(mid+1,r,e[now].rson,e[pre].rson,a);
}
int query(int l,int r,int now,int pre,int k){
if(l==r) return l;
int mid=(l+r)/2;
int ti=e[e[now].lson].num-e[e[pre].lson].num;
if(ti>=k) return query(l,mid,e[now].lson,e[pre].lson,k);
else return query(mid+1,r,e[now].rson,e[pre].rson,k-ti);
}
int main(){
while(~scanf("%d%d",&n,&q)){
cnt=0; memset(root,0,sizeof(root));
e[cnt].lson=e[cnt].rson=e[cnt].num=0;
v.clear();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++){
update(1,n,root[i],root[i-1],gain(a[i]));
}
while(q--){
int l,r,k;
scanf("%d%d",&l,&r);
ll ans=-1;
int num=r-l+1;
for(int i=1;i<=min(50,num-2);i++){
ll fi=(ll)v[query(1,n,root[r],root[l-1],num-i+1)-1];
//printf("di %d da is %lld\n",num-i+1,fi);
ll se=(ll)v[query(1,n,root[r],root[l-1],num-i)-1];
ll th=(ll)v[query(1,n,root[r],root[l-1],num-i-1)-1];
if(se+th>fi){
//printf("fi = %lld se = %lld th = %lld\n",fi,se,th);
ans=fi+se+th;
break;
}
}
printf("%lld\n",ans);
}
}
return 0;
}
/*
10 8
1 1 2 3 5 7 7 9 5 6
1 3
1 5
7 10
6 9
6 8
9 10
1000000000
*/
