Just h-index

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

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

题目就是给我们一个区间，让我们找到一个最大的值，使得大于等于这个值的数的个数大于等于这个值。

这个就是很明显的权值线段树，但是我们要找到某个区间的权值线段树，也就是要可持久化（主席树）。

然后我们二分答案即可（似乎也可以在主席树当中二分）。

每次二分check时，判断当前我们查询的区间的大于等于mid的个数即可。

AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,root[N],cnt,x;
struct node{
	int l,r,sum;
}t[N<<5];
void change(int l,int r,int &x,int y,int k){
	x=++cnt; t[x]=t[y]; t[x].sum++;
	if(l==r)	return ;	int mid=l+r>>1;
	if(k<=mid)	change(l,mid,t[x].l,t[y].l,k);
	else	change(mid+1,r,t[x].r,t[y].r,k);
}
int ask(int l,int r,int x,int y,int ql,int qr){
	if(l==ql&&r==qr)	return t[y].sum-t[x].sum;
	int mid=l+r>>1;
	if(qr<=mid)	return ask(l,mid,t[x].l,t[y].l,ql,qr);
	else if(ql>mid)	return ask(mid+1,r,t[x].r,t[y].r,ql,qr);
	else	return ask(l,mid,t[x].l,t[y].l,ql,mid)+ask(mid+1,r,t[x].r,t[y].r,mid+1,qr);
}
int bsearch(int ql,int qr){
	int l=1,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(ask(1,n,root[ql-1],root[qr],mid,n)>=mid)	l=mid;
		else	r=mid-1;
	}
	return l;
}
signed main(){
	while(~scanf("%d %d",&n,&q)){
		cnt=0;
		for(int i=1;i<=n;i++)	scanf("%d",&x),change(1,n,root[i],root[i-1],x);
		while(q--){
			int l,r;	scanf("%d %d",&l,&r);
			printf("%d\n",bsearch(l,r));
		}
	}
	return 0;
}