Keen On Everything But Triangle
题目传送门
解题思路利用主席树求区间第k小，先求区间内最大的值，再求第二大，第三大……直到找到连续的三个数可以构成一个三角形。因为对于一组数，如果不能构成三角形，就小的就是斐波那契数列，因为数的范围在10^9内，所以不会超过50个数，也就是说，我们之间这样暴力地查询，查询次数不会超过50，肯定能找到结果。
代码如下 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; inline int read(){ int res = 0, w = 0; char ch = 0; while(!isdigit(ch)){ w |= ch == '-', ch = getchar(); } while(isdigit(ch)){ res = (res << 3) + (res << 1) + (ch ^ 48); ch = getchar(); } return w ? -res : res; } const int N = 100005; int rt[N], cnt; struct T{ int l, r; int lch, rch; int sum; }tree[N << 5]; ll a[N], b[N]; int build(int l, int r) { int p = ++cnt; tree[p].l = l; tree[p].r = r; tree[p].lch = tree[p].rch = tree[p].sum = 0; if(l == r) return p; int mid = (l + r) / 2; tree[p].lch = build(l, mid); tree[p].rch = build(mid + 1, r); return p; } int insert(int k, int x) { int p = ++cnt; tree[p].l = tree[k].l; tree[p].r = tree[k].r; tree[p].lch = tree[k].lch; tree[p].rch = tree[k].rch; tree[p].sum = tree[k].sum + 1; if(tree[k].l == tree[k].r) return p; int mid = (tree[k].l + tree[k].r) / 2; if(x <= mid) tree[p].lch = insert(tree[k].lch, x); else tree[p].rch = insert(tree[k].rch, x); return p; } int query(int k1, int k2, int x) { if(tree[k1].l == tree[k1].r) return tree[k1].l; int l1 = tree[k1].lch; int l2 = tree[k2].lch; if(tree[l2].sum - tree[l1].sum >= x) return query(l1, l2, x); else { x -= tree[l2].sum - tree[l1].sum; return query(tree[k1].rch, tree[k2].rch, x); } } int main() { int n, q; while(scanf("%d%d", &n, &q) != EOF){ for(int i = 1; i <= n; i ++){ scanf("%lld", &a[i]); b[i] = a[i]; } sort(b + 1, b + n + 1); int k = unique(b + 1, b + n + 1) - b - 1; cnt = -1; rt[0] = build(1, k); for(int i = 1; i <= n; i ++){ int x = lower_bound(b + 1, b + k + 1, a[i]) - b; rt[i] = insert(rt[i - 1], x); } for(int i = 1; i <= q; i ++){ int l, r; l = read(), r = read(); if(r - l + 1 < 3){ printf("-1\n"); continue; } int x = query(rt[l - 1], rt[r], r - l + 1); int y = query(rt[l - 1], rt[r], r - l); ll ans = -1; for(int i = r - l - 1; i >= 1; i --){ int z = query(rt[l - 1], rt[r], i); if(b[y] + b[z] > b[x]){ ans = b[x] + b[y] + b[z]; break; } x = y; y = z; } printf("%lld\n", ans); } } return 0; }