题目链接http://acm.hdu.edu.cn/showproblem.php?pid=6601
题意
给出一个数组，有若干次询问。每次询问一个区间，在区间内挑出能组成三角形的三个数字，问三角形周长最大是多少。
题解
从最大的数字开始考虑，每次取紧邻的三个，如果存在三角形就输出。 最坏的情况下，数组是个斐波那契数列，这样只要取44个最大数就行了。 所以每次主席树暴力扫出前50个最大数，然后暴力扫一遍。复杂度
O
(
50
∗
Q
∗
l
o
g
n
)
O(50*Q*log_n)
O(50∗Q∗logn)
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int N
=1e5+7;
const ll mod
=998244353;
int a
[N
],aa
[N
],tmp
[60];
int rt
[N
],t
[N
*40],ls
[N
*40],rs
[N
*40],tot
=0;
int bd(int l
,int r
){
int now
=++tot
;
t
[now
]=0;
if(l
==r
) return now
;
int m
=l
+r
>>1;
ls
[now
]=bd(l
,m
);
rs
[now
]=bd(m
+1,r
);
return now
;
}
int upd(int o
,int l
,int r
,int x
){
int now
=++tot
;
t
[now
]=t
[o
]+1;
if(l
==r
) return now
;
ls
[now
]=ls
[o
];rs
[now
]=rs
[o
];
int m
=l
+r
>>1;
if(x
<=m
) ls
[now
]=upd(ls
[o
],l
,m
,x
);
else rs
[now
]=upd(rs
[o
],m
+1,r
,x
);
return now
;
}
int que(int o
,int oo
,int l
,int r
,int k
){
if(l
==r
) return (t
[oo
]-t
[o
]>=k
)?l
:0;
int m
=l
+r
>>1;
int tmp
=t
[rs
[oo
]]-t
[rs
[o
]];
if(tmp
>=k
) return que(rs
[o
],rs
[oo
],m
+1,r
,k
);
else return que(ls
[o
],ls
[oo
],l
,m
,k
-tmp
);
}
int main(){
int n
,m
;
while(scanf("%d%d",&n
,&m
)!=EOF){
int nn
=n
;
tot
=0;
for(int i
=1;i
<=n
;i
++){
scanf("%d",&a
[i
]);
aa
[i
]=a
[i
];
}
sort(aa
+1,aa
+1+n
);
n
=unique(aa
+1,aa
+1+n
)-aa
-1;
rt
[0]=bd(1,n
);
for(int i
=1;i
<=nn
;i
++){
a
[i
]=lower_bound(aa
+1,aa
+1+n
,a
[i
])-aa
;
rt
[i
]=upd(rt
[i
-1],1,n
,a
[i
]);
}
for(int i
=1,l
,r
;i
<=m
;i
++){
scanf("%d%d",&l
,&r
);
ll ans
=-1;
for(int i
=1;i
<=50;i
++){
tmp
[i
]=aa
[que(rt
[l
-1],rt
[r
],1,n
,i
)];
}
for(int i
=1,j
=2,k
=3;k
<=50&&tmp
[k
];i
++,j
++,k
++){
if(0ll+tmp
[j
]+tmp
[k
]>tmp
[i
]){
ans
=0ll+tmp
[i
]+tmp
[j
]+tmp
[k
];
break;
}
}
printf("%lld\n",ans
);
}
}
}
