HDU - 6601 Keen On Everything But Triangle 主席树

Keen On Everything But Triangle

感觉最近多校好多主席树的亚子，但是本人菜得很，还没学过主席树，看着队友写题就只能划水，\(WA\)了还不能帮忙\(debug\)，所以深思熟虑之后决定学习一下主席树。

题意

问在\([l,r]\)区间内取三个数字构成三角形，问能构成的三角形最大的周长是多少?如果不能构成三角形输出\(“-1”\)。

思路

• 三角形构成的条件：

  1. 三条边
  2. 两边之和大于第三边

• 然后呢，我们要找最大的周长，那么我们很容易想到取最大的三条边，如果不行就顺延往下。

• 我们发现询问很多，暴力肯定不行。那么其实我们会发现，不能构成三角形的条件是两边之和小于等于第三边，那么可以想到斐波那契数列是前两项之和大于第三边，那么如果一直都不符合条件，那么我们也只会找大约\(44\)次第\(k\)大的值，肯定不超时。

• 然后想明白只后我们就开始暴力了。其实就是用主席树来维护数列，在\(\log{n}\)的时间里找到第\(k\)大的值，那强行用主席树找最大、第二大...，然后暴力找出最长周长就\(ok\)了。

AC代码

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pii        pair<int, int>

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

struct Node{

    int l, r, cnt;

}node[maxn*40];

int w[maxn];

int n, m;

int cas, tol, T;

vector<int> vv;

int a[maxn];

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

    tol++;

    x = tol;

    node[x] = node[y];

    node[x].cnt++;

    if(l == r) return;

    int mid = l+r>>1;

    if(pos <= mid)

        update(l, mid, node[x].l, node[y].l, pos);

    else

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

}

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

    if(l == r)

        return l;

    int mid = l+r>>1;

    int cnt = node[node[y].l].cnt - node[node[x].l].cnt;

    if(cnt >= k)

        return query(l, mid, node[x].l, node[y].l, k);

    else

        return query(mid+1, r, node[x].r, node[y].r, k-cnt);

}

int getid(int x){

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

}

int main() {

    while(~scanf("%d%d", &n, &m)){

        vv.clear();

        tol = 0;

        mes(w, 0);

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

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

            vv.push_back(a[i]);

        }

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

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

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

            int pos = getid(a[i]);

            update(1, n, w[i], w[i-1], pos);

        }

        while(m--){

            int l, r;

            scanf("%d%d", &l, &r);

            int b[4], flag = 0;

            if(r - l + 1 < 3){

                printf("-1\n");

                continue;

            }

            b[1] = query(1, n, w[l-1], w[r], r-l+1)-1;

            b[2] = query(1, n, w[l-1], w[r], r-l)-1;

            for(int k = r-l-1; k >= 1; k--){

                b[3] = query(1, n, w[l-1], w[r], k)-1;

                if(vv[b[1]] < vv[b[2]]+vv[b[3]]){

                    printf("%lld\n", 1ll*vv[b[1]]+vv[b[2]]+vv[b[3]]);

                    flag = 1;

                    break;

                }

                for(int i = 1; i <= 2; i++)

                    b[i] = b[i+1];

            }

            if(!flag)

                printf("-1\n");

        }

    }

    return 0;

}