Just h-index

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)

Problem Description

The h-index of an author is the largest h where he has at least h papers with citations not less than h.

Bobo has published n papers with citations a1,a2,…,an respectively.
One day, he raises q questions. The i-th question is described by two integers li and ri, asking the h-index of Bobo if has only published papers with citations ali,ali+1,…,ari.

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers n and q.
The second line contains n integers a1,a2,…,an.
The i-th of last q lines contains two integers li and ri.

Output

For each question, print an integer which denotes the answer.

Constraint

  • 1≤n,q≤105
  • 1≤ai≤n
  • 1≤li≤ri≤n
  • The sum of n does not exceed 250,000.
  • The sum of q does not exceed 250,000.

Sample Input

5 3
1 5 3 2 1
1 3
2 4
1 5
5 1
1 2 3 4 5
1 5

Sample Output

2
2
2
3

题意：

给一个数组，题目再给定一些查询，在区间[x, y]中假设有一个数字ans，区间里有ans个数大于等于ans， 问ans是多少。

思路：

一道主席树的题目，因为查询的ans是多少，所以用的二分去查询这个数。

  • 首先就是建个主席树，因为题目中说ai <= n所以在建树的时候就在[1, n]中间建树就行了。
  • 然后就是查询了，如果k在l的左边，那么右边的区间肯定都是大于等于k的所以只要将T[y].sum - T[x].sum就能知道有多少个数比k来的大，然后如果k小于中间值，那么往左子树找，那么右子树肯定就都会大于k的所以直接加就行了。
  • 二分的时候也要注意一下，当得出的数值比，mid小的时候向下找，否则向上找。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 100010;
struct NODE {
    int l;
    int r;
    int sum;
};
NODE T[maxn * 50];
int root[maxn], a[maxn];
int cnt = 0;
void Updata(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) >> 1;
    if (mid >= pos) Updata(l, mid, T[x].l, T[y].l, pos);
    else Updata(mid + 1, r, T[x].r, T[y].r, pos);
}
int Query(int l, int r, int x, int y, int k) {
    if (k <= l) return T[y].sum - T[x].sum;
    int mid = (l + r) >> 1;
    if (k <= mid) return Query(l, mid, T[x].l, T[y].l, k) + T[T[y].r].sum - T[T[x].r].sum;
    else return  Query(mid + 1, r, T[x].r, T[y].r, k);
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            Updata(1, n, root[i], root[i - 1], a[i]);
        }
        while (m--) {
            int x, y, ans = 0;
            scanf("%d %d", &x, &y);
            int l = 0, r = n;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (Query(1, n, root[x - 1], root[y], mid) < mid) r = mid;
                else l = mid;
            }
            printf("%d\n", l);
        }
    }
    return 0;
}