CJust h-index

链接：https://ac.nowcoder.com/acm/contest/1107/C 来源：牛客网  

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K Special Judge, 64bit IO Format: %lld

题目描述

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,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​ respectively. One day, he raises q questions. The i-th question is described by two integers lil_ili​ and rir_iri​, asking the h-index of Bobo if has *only* published papers with citations ali,ali+1,…,aria_{l_i}, a_{l_i + 1}, \dots, a_{r_i}ali​​,ali​+1​,…,ari​​.

输入描述:

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,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​. The i-th of last q lines contains two integers lil_ili​ and rir_iri​.

输出描述:

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

示例1

输入

复制

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

输出

复制

2 2 2 3

备注:

* 1≤n,q≤1051 \leq n, q \leq 10^51≤n,q≤105 * 1≤ai≤n1 \leq a_i \leq n1≤ai​≤n * 1≤li≤ri≤n1 \leq l_i \leq r_i \leq n1≤li​≤ri​≤n * The sum of n does not exceed 250,000. * The sum of q does not exceed 250,000.

 

#include<bits/stdc++.h> using namespace std; const int MAXN = 150010; const int M = MAXN * 30; int tot, a[MAXN]; int T[M], lson[M], rson[M], c[M]; int build(int l, int r) { int root = tot++; c[root] = 0; if (l != r) { int mid = (l + r) >> 1; lson[root] = build(l, mid); rson[root] = build(mid + 1, r); } return root; } int update(int root, int pos, int val, int m) { int newroot = tot++, tmp = newroot; c[newroot] = c[root] + val; int l = 1, r = m; while (l < r) { int mid = (l + r) >> 1; if (pos <= mid) { lson[newroot] = tot++; rson[newroot] = rson[root]; newroot = lson[newroot]; root = lson[root]; r = mid; } else { rson[newroot] = tot++; lson[newroot] = lson[root]; newroot = rson[newroot]; root = rson[root]; l = mid + 1; } c[newroot] = c[root] + val; } return tmp; } int query(int left_root, int right_root, int l, int r, int w) { //cout << c[left_root] << " " << c[right_root] << " " << l << " " << r << " " << w << "\n"; if (l == r) { return l; } int mid = (l + r) >> 1; if (c[rson[right_root]] - c[rson[left_root]] + w >= mid + 1) { return query(rson[left_root], rson[right_root], mid + 1, r, w); } else { return query(lson[left_root], lson[right_root], l, mid, w + c[rson[right_root]] - c[rson[left_root]]); } } const int K = 100005; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; while (cin >> n >> m) { tot = 0; T[0] = build(1, K); for (int i = 1; i <= n; i++) { cin >> a[i]; T[i] = update(T[i - 1], a[i], 1, K); } while (m--) { int a, b; cin >> a >> b; cout << query(T[a - 1], T[b], 1, K, 0) << "\n"; } } return 0; }