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;

}

巴特西

2019杭电多校第二场hdu6601 Keen On Everything But Triangle

Keen On Everything But Triangle

解题思路

代码如下

最新文章

热门文章