主席树的妙用——Just h-index

题目传送门：https://ac.nowcoder.com/acm/contest/1107/C

题意：给出一个区间，求最大的 h ，使得区间内至少有 h 个数大于等于 h.

思路：1.需要区间有序，那么就需要使用主席树。

　　　2.二分答案。

　　　　2.1 —— 一开始我的思路是直接对每一个查询二分答案 h。

　　　　　　　　然后判断第 len(区间个数)-h+1 小是否大于等于 h，这样二分得出最大h，但是T了。

　　　　　　　　一开始以为是卡常了，于是各种骚操作还是没有什么卵用。

　　　　　　　　于是在一次优化 “ 由于n小可以去掉离散化” ，依然T了之后。忽然发现可以直接二分位置，也就是直接在主席树查询中直接找到答案。

　　　　2.2 —— 在查询过程中，我们就不断的二分位置，判定条件是：

　　　　　　　　主席树中，

　　　　　　　　h右边的个数是否大于h，如果是，那么就往右子树走，否则就往左子树走。

　　　　　　　　记得不要离散化，因为我们二分的是位置，而不是大小。

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

typedef double dou;

typedef long long ll;

typedef pair<int, int> pii;

typedef map<int, int> mii;

#define pai acos(-1.0)

#define M 4000005

#define inf 0x3f3f3f3f

#define mod 1000000007

#define IN inline

#define W(a) while(a)

#define lowbit(a) a&(-a)

#define left k<<1

#define right k<<1|1

#define lson L, mid, left

#define rson mid + 1, R, right

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

#define Abs(a) (a ^ (a >> 31)) - (a >> 31)

#define random(a,b) (rand()%(b+1-a)+a)

#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int n, cnt, Q;

int  num[M];

int T[M], Ls[M], Rs[M], sum[M];

IN int Built(int L, int R) {

    int rt = ++cnt;

    if (L < R) {

        int mid = (L + R) >> ;

        Ls[rt] = Built(L, mid);

        Rs[rt] = Built(mid + , R);

    }

    return rt;

}

IN int updata(int L, int R, int pre, int id) {

    int rt = ++cnt;

    Ls[rt] = Ls[pre], Rs[rt] = Rs[pre], sum[rt] = sum[pre] + ;

    if (L < R) {

        int mid = (L + R) >> ;

        if (id <= mid)Ls[rt] = updata(L, mid, Ls[pre], id);

        else Rs[rt] = updata(mid + , R, Rs[pre], id);

    }

    return rt;

}

//Rtot是上一个节点的右子节点的个数

IN int query(int u, int v, int L, int R, int Rtot) {

    if (L == R)return L;

    int R_sum = sum[Rs[v]] - sum[Rs[u]];//右子节点的个数

    int mid = (L + R) >> ;

    //判定条件

    if (mid - Rtot +  > R_sum)return query(Ls[u], Ls[v], L, mid, Rtot + R_sum);

    else return query(Rs[u], Rs[v], mid + , R, Rtot);

}

IN int read() {//读入挂

    int x = ; bool f = ; char ch = getchar();

    while (ch < '' || '' < ch)

        f |= ch == '-', ch = getchar();

    while ('' <= ch && ch <= '')

        x = x *  + ch - '', ch = getchar();

    return f ? -x : x;

}

int main() {

    W(scanf("%d%d", &n, &Q) != EOF) {

        cnt = ;

        T[] = Built(, n);

        for (register int i = ; i <= n; i++)num[i] = read();

        for (register int i = ; i <= n; i++)T[i] = updata(, n, T[i - ], num[i]);

        int l, r;

        W(Q--) {

            l = read(), r = read();

            printf("%d\n", query(T[l - ], T[r], , n, ));

        }

    }

    return ;

}

巴特西

主席树的妙用——Just h-index

最新文章

热门文章