hdu 6278 Just h-index

题意：

定义H为 ：如果区间内有H个大于等于H的paper，则是h-index

给你一个长度为  的序列，  次询问，每一次询问求区间内最大的H。

1、针对每一个区间，二分H，然后每次用主席树找出小于等于H-1的数的数量，然后减一下做判断就可以了。

#include <bits/stdc++.h>
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
	int l;
	int r;
	int sum;
	node() { sum = 0; }
}tree[100005 * 20];
int n, m, cnt, a[100005], t[100005], root[100005], ql, qr;
void init()
{
	root[0] = 0;
	tree[0].l = tree[0].r = tree[0].sum = 0;
	cnt = 1;
}
void build(int num, int &rot, int left, int right)
{
	tree[cnt] = tree[rot];
	rot = cnt++;
	tree[rot].sum++;
	if (left == right)
		return;
	imid;
	if (num <= mid)
		build(num, tree[rot].l, left, mid);
	else
		build(num, tree[rot].r, mid + 1, right);
}
int query(int pre, int nex, int k, int left, int right)
{
	int s = tree[tree[nex].l].sum - tree[tree[pre].l].sum;
	if (left == right)
		return 0;
	imid;
	if (k < mid)
		return query(tree[pre].l, tree[nex].l, k, left, mid);
	else if (k > mid)
		return s + query(tree[pre].r, tree[nex].r, k, mid + 1, right);
	else
		return s;
}
int judge(int k)
{
	int ans = query(root[ql - 1], root[qr], k - 1, 1, n);
	if (k <= qr - ql + 1 - ans)
		return 1;
	return 0;
}
int main()
{
	while (scanf("%d%d", &n, &m) > 0)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
		}
		init();
		for (int i = 1; i <= n; i++)
		{
			root[i] = root[i - 1];
			build(a[i], root[i], 1, n);
		}
		while (m--)
		{
			scanf("%d%d", &ql, &qr);
			int l = 0, r = qr - ql + 1;
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				if (judge(mid))
					l = mid;
				else
					r = mid - 1;
			}
			if (judge(r))
				l = r;
			printf("%d\n", l);
		}
	}
}