hdu-6601 Keen On Everything But Triangle

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=6601

Description

N sticks are arranged in a row, and their lengths are a1,a2,...,aN.

There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.

Input

There are multiple test cases.

Each case starts with a line containing two positive integers N,Q(N,Q≤105).

The second line contains N integers, the i-th integer ai(1≤ai≤109) of them showing the length of the i-th stick.

Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.

It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×105.

Output

For each test case, output Q lines, each containing an integer denoting the maximum circumference.

Sample Input

5 3

2 5 6 5 2

1 3

2 4

2 5

Sample Output

13

16

16

Hint

题意

给一个长度为N的数组，Q个询问，(l, r)区间内任三个数能构成的三角形的最大周长

题解：

对于排序好的数组，若想要构成三角形周长最大，肯定从最大的边开始取，且三条边是连续的，也就是先取第一大第二大第三大，若不能构成三角形则取第二大第三大第四大，依次取下去。

未排序的数组可以用主席数查询第K大，对于每次询问最多只要查询四十多次，因为若要构造出不能构成三角形的数组，最优构造策略是斐波那契数列，1,2,3,5,8,11,19，到四十多项就超过1e9了。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int mx = 1e5+5;

typedef long long ll;

int a[mx], root[mx], cnt;

vector <int> v;

struct node {

   int l, r, sum;

}T[mx*40];

int getid(int x) {

   return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;

}

void update(int l, int r, int &x, int y, int pos) {

   T[++cnt] = T[y]; T[cnt].sum++; x = cnt;

   if (l == r) return;

   int mid = (l+r) / 2;

   if (mid >= pos) update(l, mid, T[x].l, T[y].l, pos);

   else update(mid+1, r, T[x].r, T[y].r, pos);

}

int query(int l, int r, int x, int y, int k) {

   if (l == r) return l;

   int mid = (l+r) / 2;

   int sum = T[T[y].l].sum - T[T[x].l].sum;

   if (sum >= k) return query(l, mid, T[x].l, T[y].l, k);

   else return query(mid+1, r, T[x].r, T[y].r, k-sum);

}

int main() {

    int n, m;

    while (scanf("%d%d", &n, &m) != EOF) {

        v.clear();  cnt = 0;

        for (int i = 1; i <= n; i++) {

            scanf("%d", &a[i]);

            v.push_back(a[i]);

        }

        sort(v.begin(), v.end());

        v.erase(unique(v.begin(), v.end()), v.end());

        for (int i = 1; i <= n; i++) update(1, n, root[i], root[i-1], getid(a[i]));

        for (int i = 1; i <= m; i++) {

            int x, y;

            scanf("%d%d", &x, &y);

            bool flag = false;

            int len = y - x + 1;

            for (int j = 1; j <= y-x-1; j++) {

                ll a = v[query(1, n, root[x-1], root[y], len-j+1)-1];

                ll b = v[query(1, n, root[x-1], root[y], len-(j+1)+1)-1];

                ll c = v[query(1, n, root[x-1], root[y], len-(j+2)+1)-1];

                if (b+c > a) {

                    flag = true;

                    printf("%lld\n", a+b+c);

                    break;

                }

            }

            if (!flag) puts("-1");

        }

    }

    return 0;

}

巴特西