原题： http://acm.hdu.edu.cn/showproblem.php?pid=6601
题意：
给出n数组，每次询问，求出区间内的数可组成的周长最大的三角形。
解析：
显然在对区间排序后，答案的三个数一定连续。
考虑三个连续的数不能组成三角形的情况：有 a + b < = c a+b<=c a+b<=c
那么极限的情况应该是： 1 , 1 , 2 , 3 , 5 , 8 , 13... 1,1,2,3,5,8,13... 1,1,2,3,5,8,13...，到了40多项就大于1e9了，所以说，只需要求出区间的最大的50个数即可得到答案。
这个东西用主席树做一下就行。
代码：
#include<bits/stdc++.h> using namespace std; #define N 100005 #define LL long long int root[N]; int siz[N*40],lchild[N*40],rchild[N*40]; int tot; void insert(int last,int cur,int L,int R,int k) { //单点更新 siz[cur]=siz[last]+1;//将前一个树的信息复制过来 lchild[cur]=lchild[last]; rchild[cur]=rchild[last]; if(L==R) return ; int mid=L+R>>1; if(k<=mid) insert(lchild[last],lchild[cur]=++tot,L,mid,k);//对于需要更改的节点都需要新增节点 else insert(rchild[last],rchild[cur]=++tot,mid+1,R,k); } int query(int last,int cur,int k,int L,int R) { if(L==R) return L; int mid=L+R>>1; int lsum=siz[lchild[cur]]-siz[lchild[last]]; if(lsum>=k) return query(lchild[last],lchild[cur],k,L,mid); else return query(rchild[last],rchild[cur],k-lsum,mid+1,R); } int a[N],b[N],n,m,l,r,k; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(siz,0,sizeof siz); memset(lchild,0,sizeof lchild); memset(rchild,0,sizeof rchild); tot=0; for(int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int t=unique(b+1,b+n+1)-b-1; for(int i=1; i<=n; i++) insert(root[i-1],root[i]=++tot,1,t,lower_bound(b+1,b+t+1,a[i])-b); for(int i=0; i<m; i++) { vector<int>v(52); scanf("%d%d",&l,&r); for(int j=1; j<=min(50,r-l+1); j++) { v[j]=(b[query(root[l-1],root[r],r-l+2-j,1,t)]); } LL ans=-1; for(int i=1; i+2<=min(50,r-l+1); i++) { if(v[i+1]+v[i+2]>v[i]) { ans=(LL)v[i+1]+(LL)v[i+2]+(LL)v[i]; break; } } printf("%lld\n",ans); } } }