1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
| #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 10;
struct node { int ls, rs, sum; } ns[MAXN * 20];
int ct; int rt[MAXN * 20];
void cpy(int& now, int old) { now = ++ct; ns[now] = ns[old]; }
void pushUp(int& now) { ns[now].sum = ns[ns[now].ls].sum + ns[ns[now].rs].sum; }
void build(int& now, int l, int r) { now = ++ct; ns[now].sum = 0; if (l == r) return; int m = (l + r) >> 1; build(ns[now].ls, l, m); build(ns[now].rs, m + 1, r); }
void update(int& now, int old, int l, int r, int x) { cpy(now, old); if (l == r) { ns[now].sum++; return; } int m = (l + r) >> 1; if (x <= m) update(ns[now].ls, ns[old].ls, l, m, x); else update(ns[now].rs, ns[old].rs, m + 1, r, x); pushUp(now); }
int query(int s, int t, int l, int r, int k) { if (l == r) return l; int m = (l + r) >> 1; int cnt = ns[ns[t].ls].sum - ns[ns[s].ls].sum; if (k <= cnt) return query(ns[s].ls, ns[t].ls, l, m, k); return query(ns[s].rs, ns[t].rs, m + 1, r, k - cnt); }
void init(int n) { ct = 0; build(rt[0], 1, n); }
int a[MAXN], b[MAXN]; int c[MAXN];
int main() { int n, m; while (cin >> n >> m) { for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(b + 1, b + n + 1); int sz = unique(b + 1, b + 1 + n) - b - 1; init(sz); for (int i = 1; i <= n; i++) { a[i] = lower_bound(b + 1, b + 1 + sz, a[i]) - b; update(rt[i], rt[i - 1], 1, sz, a[i]); } while (m--) { int s, t, k; scanf("%d%d", &s, &t); if(t - s + 1 < 3) printf("-1\n"); else { int cnt = 0, flag = 0; for(int i = t - s + 1; i > 0; --i) { c[cnt] = b[query(rt[s - 1], rt[t], 1, sz, i)]; if(cnt > 1 && c[cnt - 2] < c[cnt - 1] + c[cnt]) { printf("%lld\n", c[cnt - 2] * 1ll + c[cnt - 1] * 1ll + c[cnt] * 1ll); flag = 1; break; } ++cnt; } if(!flag) printf("-1\n"); } } } return 0; }
|