题意：给定一个长为n的序列，有q次询问，每次询问[l,r]这段区间内挑三个数，能组成的三角形的最大周长，无解输出-1
n,q<=1e5，a[i]<=1e9
思路：题解写法和我的不太一样
先说题解做法，显然最坏情况下是斐波那契数列的形式，大概是log2(1e9)项就没有-1了，所以维护一个可以取某一段中前50大的数字的数据结构，取出来之后sort看相邻3个取max即可
我的做法是用主席树把区间权值抠出来，树上二分权值，如果当前结点的右儿子的size>=3就必定是最优解，否则把右儿子中的所有数取出来再递归左儿子，最后同sort处理
原理应该差不多
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 typedef unsigned int uint;
5 typedef unsigned long long ull;
6 typedef pair<int,int> PII;
7 typedef pair<ll,ll> Pll;
8 typedef vector<int> VI;
9 #define N 110000
10 #define M 1100000
11 #define fi first
12 #define se second
13 #define MP make_pair
14 #define pi acos(-1)
15 #define mem(a,b) memset(a,b,sizeof(a))
16 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
17 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
18 #define lowbit(x) x&(-x)
19 #define Rand (rand()*(1<<16)+rand())
20 #define id(x) ((x)<=B?(x):m-n/(x)+1)
21 #define ls p<<1
22 #define rs p<<1|1
23
24 const ll MOD=998244353,inv2=(MOD+1)/2;
25 double eps=1e-6;
26 ll INF=1e14;
27
28 struct arr
29 {
30 int l,r,s;
31 }t[N*50];
32
33 int c[N],root[N],flag,m,cnt;
34 ll ans;
35
36 int read()
37 {
38 int v=0,f=1;
39 char c=getchar();
40 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
41 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
42 return v*f;
43 }
44
45 void update(int l,int r,int x,int &p)
46 {
47 t[++cnt]=t[p];
48 p=cnt;
49 t[p].s++;
50 if(l==r) return;
51 int mid=(l+r)>>1;
52 if(x<=mid) update(l,mid,x,t[p].l);
53 else update(mid+1,r,x,t[p].r);
54 }
55
56 int find(int l,int r,int x,int p1,int p2)
57 {
58 //printf("find l=%d r=%d\n",l,r);
59 int tmp=t[p2].s-t[p1].s;
60 if(x<=0) return 0;
61 if(!tmp) return 0;
62 if(l==r)
63 {
64 rep(i,1,min(3,tmp)) c[++m]=l;
65 return min(3,tmp);
66 }
67 int mid=(l+r)>>1;
68 x-=find(mid+1,r,x,t[p1].r,t[p2].r);
69 find(l,mid,x,t[p1].l,t[p2].l);
70 return tmp;
71 }
72
73 void query(int l,int r,int p1,int p2)
74 {
75 if(l>r) return;
76 if(l==r)
77 {
78 rep(i,1,min(3,t[p2].s-t[p1].s)) c[++m]=l;
79 return;
80 }
81 int mid=(l+r)>>1;
82 int tmp=t[t[p2].r].s-t[t[p1].r].s;
83 if(tmp>=3)
84 {
85 find(mid+1,r,3,t[p1].r,t[p2].r);
86 return;
87 }
88 else
89 {
90 if(tmp) find(mid+1,r,tmp,t[p1].r,t[p2].r);
91 query(l,mid,t[p1].l,t[p2].l);
92 }
93 }
94
95
96 int main()
97 {
98 int n,q;
99 while(scanf("%d%d",&n,&q)!=EOF)
100 {
101 rep(i,1,cnt) t[i].l=t[i].r=t[i].s=0;
102 cnt=1; root[0]=1;
103 rep(i,1,n)
104 {
105 int x=read();
106 root[i]=root[i-1];
107 update(1,1e9,x,root[i]);
108 }
109 while(q--)
110 {
111 int x=read(),y=read();
112 ans=0;
113 m=0;
114 flag=0;
115 query(1,1e9,root[x-1],root[y]);
116 //printf("flag=%d\n",flag);
117 sort(c+1,c+m+1);
118 //printf("m=%d\n",m);
119 //rep(i,1,m) printf("%d\n",c[i]);
120 rep(i,2,m-1)
121 if(c[i]+c[i-1]>c[i+1]) ans=max(ans,0ll+c[i-1]+c[i]+c[i+1]);
122
123 if(ans==0) printf("-1\n");
124 else printf("%I64d\n",ans);
125 rep(i,1,m) c[i]=0;
126 }
127
128
129 }
130 return 0;
131 }