題目連結:https://vjudge.net/problem/HDU-6601
題意:區間組成最大的三角形周長是多少
題解:根據斐波那契的性質,在1e9内最多有47個數就一定能組成三角形,是以線段樹維護下區間的前50大的數,然後每次查詢的時候用滾動數組更新一下即可,當然也可以用主席樹寫,先離散化,記錄下每個數的數目,查詢前50大即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
struct node {
int l, r, len;
int val[52];
}tree[N << 2];
int n, m, a[N];
int q[2][65];
int qlen[2];
int pos;
void pushup(int cur) {
tree[cur].len = 0;
int len1 = 1, len2 = 1;
while(tree[cur].len < 50 && (len1 <= tree[cur << 1].len || len2 <= tree[cur << 1 | 1].len)) {
if(len2 > tree[cur << 1 | 1].len || (len1 <= tree[cur << 1].len && tree[cur << 1].val[len1] >= tree[cur << 1 | 1].val[len2])) {
tree[cur].len++;
tree[cur].val[tree[cur].len] = tree[cur << 1].val[len1];
len1++;
} else {
tree[cur].len++;
tree[cur].val[tree[cur].len] = tree[cur << 1 | 1].val[len2];
len2++;
}
}
}
void build(int l, int r, int cur) {
tree[cur].l = l;
tree[cur].r = r;
if(l == r) {
tree[cur].val[1] = a[l];
tree[cur].len = 1;
return;
}
int mid = (r + l) >> 1;
build(l, mid, cur << 1);
build(mid + 1, r, cur << 1 | 1);
pushup(cur);
}
void query(int pl, int pr, int cur) {
if(pl <= tree[cur].l && tree[cur].r <= pr) {
qlen[pos ^ 1] = 0;
int i = 1, j = 1;
while(qlen[pos ^ 1] < 50 &&(i <= qlen[pos] || j <= tree[cur].len)) {
if(j > tree[cur].len || (i <= qlen[pos] && q[pos][i] >= tree[cur].val[j])) {
qlen[pos ^ 1] ++;
q[pos ^ 1][qlen[pos ^ 1]] = q[pos][i];
i++;
} else {
qlen[pos ^ 1] ++;
q[pos ^ 1][qlen[pos ^ 1]] = tree[cur].val[j];
j++;
}
}
pos = pos ^ 1;
return;
}
if(pl <= tree[cur << 1].r) query(pl, pr, cur << 1);
if(pr >= tree[cur << 1 | 1].l) query(pl, pr, cur << 1 | 1);
return;
}
int main() {
int l, r;
ll ans, cnt1, cnt2;
while(~scanf("%d %d", &n, &m)) {
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, n, 1);
while(m--) {
scanf("%d %d", &l, &r);
qlen[0] = qlen[1] = 0;
pos = 0;
query(l, r, 1);
if(qlen[pos] <= 2) {
printf("-1\n");
continue;
}
ans = 0;
for(int i = 1; i + 2 <= qlen[pos]; i++) {
if(q[pos][i] < q[pos][i + 1] + q[pos][i + 2]) {
ans = 1LL * q[pos][i] + q[pos][i + 1] + q[pos][i + 2];
break;
}
}
if(ans == 0) printf("-1\n");
else printf("%lld\n", ans);
}
}
return 0;
}