题意：
给定序列a，ai为第i根木棍长度，给出q个询问
每次问[L,R]内能构成三角形的最大周长是多少
题解：
属于那种没有往这个方向想就很难想到，然后一直想不到的题2333
因为周长要最大，贪心地优先考虑第一大，第二大，第三大能不能组成合法的三角形
假设不行，那第一根肯定是废了
因为任意两边之和大于第三边->最小的两边之和要大于第三边
第二和第三都搞不定第一，那其他的更不行
接下来继续考虑第二大，第三大，第四大...
但是会担心复杂度怎么办？
怎么办？考虑最坏情况，一直找不到，且构成斐波那契关系
则斐波那契的第45项数已经超过1e9了
说明如果有答案，则在45次内必能找到
如果-1，也能在45次内确定（因此区间长度>=45的话肯定是会有答案的，如果一定没有，则在45次内也能知道，不会tle）
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) typedef long long ll; using namespace std; const int N=2e5+5; const int maxn=N*40; int cnt,n,m,q; int b[N],a[N],tmp[N]; struct pesis_seg{ int ls[maxn],rs[maxn],rt[maxn],sum[maxn]; void build(int &o,int l,int r){ o=++cnt; if(l==r) { return; } int mid=(l+r)>>1; build(ls[o],l,mid); build(rs[o],mid+1,r); } int update(int o,int l,int r,int pos){ int oo=++cnt;//相当于动态开点 ls[oo]=ls[o];rs[oo]=rs[o];sum[oo]=sum[o]+1; if(l==r){ return oo; } int mid=(l+r)>>1; if(pos<=mid) ls[oo]=update(ls[o],l,mid,pos); else rs[oo]=update(rs[o],mid+1,r,pos); return oo; } int query(int kth,int u,int v,int l,int r){ if(l==r){ return l; } int mid=(l+r)>>1; int x=sum[ls[v]]-sum[ls[u]]; //cout<<kth<<" "<<u<<" "<<v<<" "<<l<<" "<<r<<" "<<x<<endl; if(x>=kth) return query(kth,ls[u],ls[v],l,mid); else return query(kth-x,rs[u],rs[v],mid+1,r); } }t; int main(){ //fastio; //freopen("lys.in","r",stdin); //freopen("lys.in","r",stdin); while(scanf("%d %d",&n,&q)!=EOF){ for(int i=1;i<=cnt;i++) t.rt[i]=t.sum[i]=t.ls[i]=t.rs[i]=0; cnt=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+n+1); int len=unique(b+1,b+n+1)-(b+1); t.build(t.rt[0],1,len); for(int i=1;i<=n;i++){ // int update(int o,int pre,int l,int r,int pos,int val){ int pos=lower_bound(b+1,b+len+1,a[i])-b; t.rt[i]=t.update(t.rt[i-1],1,len,pos); } for(int ii=1;ii<=q;ii++){ int l,r; scanf("%d%d",&l,&r); int mx=r-l+1; bool flag=false; int v[5]; for(int i=1;i<=mx-2;i++){ v[1]=b[t.query(mx-i+1,t.rt[l-1],t.rt[r],1,len)]; v[2]=b[t.query(mx-i,t.rt[l-1],t.rt[r],1,len)]; v[3]=b[t.query(mx-i-1,t.rt[l-1],t.rt[r],1,len)]; if(v[1]<v[2]+v[3]){ flag=true; ll ans=(ll)v[1]+v[2]+v[3]; printf("%lld\n",ans); break; } } if(!flag) printf("%d\n",-1); } } }