有两个结论：1.排序后，答案一定是连续的三个数；2.当序列长度超过44一定有三个相同的数（因为即使该序列是斐波那契数列，此时也超过了1e9），然后用主席树等数据结构（略卡常，建议主席树）来维护前45大即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define mid (l+r>>1) 5 #define inf 1000000000 6 int V,n,m,k,x,y,a[N],b[N],r[N],f[N*20],ls[N*20],rs[N*20]; 7 void update(int k1,int &k2,int l,int r,int x){ 8 k2=++V; 9 ls[k2]=ls[k1]; 10 rs[k2]=rs[k1]; 11 f[k2]=f[k1]+1; 12 if (l==r)return; 13 if (x<=mid)update(ls[k1],ls[k2],l,mid,x); 14 else update(rs[k1],rs[k2],mid+1,r,x); 15 } 16 int query(int k1,int k2,int l,int r,int p){ 17 if (l==r)return l; 18 if (f[rs[k2]]-f[rs[k1]]>=p)return query(rs[k1],rs[k2],mid+1,r,p); 19 return query(ls[k1],ls[k2],l,mid,p-f[rs[k2]]+f[rs[k1]]); 20 } 21 int main(){ 22 while (scanf("%d%d",&n,&m)!=EOF){ 23 V=0; 24 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 25 for(int i=1;i<=n;i++)b[i]=a[i]; 26 sort(b+1,b+n+1); 27 int k=unique(b+1,b+n+1)-b-1; 28 for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+k+1,a[i])-b; 29 for(int i=1;i<=n;i++)update(r[i-1],r[i]=++V,1,k,a[i]); 30 for(int i=1;i<=m;i++){ 31 scanf("%d%d",&x,&y); 32 int ma=min(y-x+1,45),flag=0; 33 for(int j=1;j<=ma;j++){ 34 a[j]=query(r[x-1],r[y],1,k,j); 35 if ((j>2)&&(b[a[j-1]]+b[a[j]]>b[a[j-2]])){ 36 printf("%lld\n",0LL+b[a[j]]+b[a[j-1]]+b[a[j-2]]); 37 flag=1; 38 break; 39 } 40 } 41 if (!flag)printf("-1\n"); 42 } 43 } 44 }