题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6278
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
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.
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.
## 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.
题意：
一个作者它的“h-index”指的是：有一个最大的正整数h，且满足他有至少h篇论文的引用量不低于h。
现在给出n篇论文的引用量，m个区间[L,R]的查询，询问假设他只发了[L,R]这个区间内的这些论文，则他的h-index为多少。
题解：
当初比赛的时候不会主席树，也不会莫队，只能拿着普通的线段树在那里硬刚，结果十分凄惨。
现在会了分块版的莫队算法，回来补题了。
考虑num[c]表示引用量为c的文章数，那么用树状数组维护就可以 $O\left( {\log _2 N} \right)$ 的进行单点修改、区间查询，正好符合题目要求；
所以我们每次区间转移进行 $O\left( {\log _2 N} \right)$ 的进行单点修改，
然后转移结束之后，当前区间的答案（h_index）就可以通过 二分查找 + $O\left( {\log _2 N} \right)$ 的区间查询 得到。
时间复杂度大概在 $O\left( {N \cdot \sqrt N \cdot \left( {\log _2 N} \right)^2 } \right)$，从理论上讲应该可以过。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+;
const int MAXM=1e5+; int n,m;
int citation[MAXN];
int h_idx[MAXM];
struct Query
{
int block;
int id;
int l,r;
bool operator <(const Query &oth) const
{
if(block==oth.block) return r<oth.r;
return block<oth.block;
}
}query[MAXM]; struct _BIT{
int N,C[MAXN];
int lowbit(int x){return x&(-x);}
void init(int n)//初始化共有n个点
{
N=n;
for(int i=;i<=N;i++) C[i]=;
}
void add(int pos,int val)//在pos点加上val
{
while(pos<=N)
{
C[pos]+=val;
pos+=lowbit(pos);
}
}
int sum(int pos)//查询1~pos点的和
{
int ret=;
while(pos>)
{
ret+=C[pos];
pos-=lowbit(pos);
}
return ret;
}
}BIT; int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int len=sqrt(n);
for(int i=;i<=n;i++) scanf("%d",&citation[i]); for(int i=;i<=m;i++)
{
scanf("%d%d",&query[i].l,&query[i].r);
query[i].block=query[i].l/len;
query[i].id=i;
}
sort(query+,query+m+); BIT.init(n);
int pl=;
int pr=;
int cnt=;
for(int i=;i<=m;i++)
{
if(pr<query[i].r)
{
for(int j=pr+;j<=query[i].r;j++)
{
BIT.add(citation[j],);
cnt++;
}
}
if(pr>query[i].r)
{
for(int j=pr;j>query[i].r;j--)
{
BIT.add(citation[j],-);
cnt--;
}
}
if(pl<query[i].l)
{
for(int j=pl;j<query[i].l;j++)
{
BIT.add(citation[j],-);
cnt--;
}
}
if(pl>query[i].l)
{
for(int j=pl-;j>=query[i].l;j--)
{
BIT.add(citation[j],);
cnt++;
}
}
pl=query[i].l;
pr=query[i].r; int l=,r=n,mid;
while(l<r)
{
mid=(l+r+)/;
if(cnt-BIT.sum(mid-)<mid) r=mid-;
else l=mid;
} h_idx[query[i].id]=r;
} for(int i=;i<=m;i++) printf("%d\n",h_idx[i]);
}
}