链接： HDU6601 Keen On Everything But Triangle
题意：
给出一段长度为N的序列a[1]、a[2]、… 、a[N]，Q次询问，每次询问[L, R]区间（a[L] ~ a[R]）内构成的三角形周长最长的是多少?
其中 N,Q ≤ 105，1 ≤ a[i] ≤ 109
分析：
三角形构成条件：两边之和大于第三边。
要求构成最大的三角形；
所以 每次从区间里面选最大的3个 进行讨论，例如排好后是 q[1]≥q[2]≥q[3]≥q[4]≥q[5]…，先讨论q[1],q[2],q[3]，若q[2]+q[3]>q[1]，则符合，ans=q[1]+q[2]+q[3]；否则舍弃q[1]，继续讨论 q[2],q[3],q[4]，以此类推。
如果每次这样处理总的时间复杂度达到O(Q*NlogN)
但是，我们可以假设，如果排好序了进行查找，每次都不符合，即 每次都有 q[i] ≥ q[i+1]+q[i+2]，根据斐波那契数列，可以发现，因为a[i] ≤ 109，一直不符合的项数不可能超过50（实际上40多项就已经达到 109），所以我们每次只要查找前 min (50, R-L+1) 项就行。
这样就不必对区间所有元素排序，只需要找到前50大的数，于是可以用主席树来静态查找第K大的数，最终时间复杂度O(Q*50logN)。
以下代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+50;
int N,Q,n,a[maxn],b[maxn],root[maxn];
int t[maxn<<5],ls[maxn<<5],rs[maxn<<5],cnt;
void init()
{
for(int i=1;i<=N;i++)b[i]=a[i];sort(b+1,b+N+1);n=unique(b+1,b+N+1)-(b+1);for(int i=1;i<=N;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
}
int build(int l,int r)
{
int rt=++cnt;if(l==r){
t[rt]=0;return rt;}int mid=(l+r)>>1;ls[rt]=build(l,mid);rs[rt]=build(mid+1,r);t[rt]=t[ls[rt]]+t[rs[rt]];return rt;
}
int updata(int l,int r,int pos,int pre)
{
int rt=++cnt;if(l==r){
t[rt]=t[pre]+1;return rt;}ls[rt]=ls[pre],rs[rt]=rs[pre];int mid=(l+r)>>1;if(pos<=mid)ls[rt]=updata(l,mid,pos,ls[pre]);elsers[rt]=updata(mid+1,r,pos,rs[pre]);t[rt]=t[ls[rt]]+t[rs[rt]];return rt;
}
int query(int l,int r,int rt1,int rt2,int k)
{
if(l==r)return l;int suml=t[ls[rt2]]-t[ls[rt1]];int mid=(l+r)>>1;if(suml>=k)return query(l,mid,ls[rt1],ls[rt2],k);elsereturn query(mid+1,r,rs[rt1],rs[rt2],k-suml);
}
int main()
{
while(~scanf("%d %d",&N,&Q)){
cnt=0;for(int i=1;i<=N;i++)scanf("%d",&a[i]);init();root[0]=build(1,n);for(int i=1;i<=N;i++)root[i]=updata(1,n,a[i],root[i-1]);while(Q--){
int L,R;scanf("%d %d",&L,&R);LL ans=-1,q[100]; //结果会爆int，要开long longfor(int i=1;i<=min(50,R-L+1);i++){
q[i]=1LL*b[query(1,n,root[L-1],root[R],R-L+2-i)];if(i>=3&&q[i]+q[i-1]>q[i-2]){
ans=q[i]+q[i-1]+q[i-2];break;}}printf("%lld\n",ans);}}return 0;
}