Just h-index

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 $a_1, a_2, \dots, a_n$ .
The i-th of last q lines contains two integers $l_i$ and $r_i$ .

C++11(clang++ 3.9) 解法, 执行用时: 323ms, 内存消耗: 23032K, 提交时间: 2019-10-02 22:28:48

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
int a[maxn],root[maxn],cnt,n,q;
struct node{int l,r,sum;}T[maxn*40];
inline void update(int l,int r,int &x,int y,int pos)
{
	T[++cnt]=T[y];T[cnt].sum++;x=cnt;
	if(l==r)return ;
	int m=(l+r)>>1;
	if(m>=pos) update(l,m,T[x].l,T[y].l,pos);
	else update(m+1,r,T[x].r,T[y].r,pos);
}
inline int query(int l,int r,int x,int y,int k)
{
	if(l==r)return l;
	int m=(l+r)>>1;int sum=T[T[y].r].sum-T[T[x].r].sum;
	if(sum+k<=m) return query(l,m,T[x].l,T[y].l,k+sum);
	else return query(m+1,r,T[x].r,T[y].r,k);
}
int main()
{
	while(scanf("%d%d",&n,&q)!=EOF)
	{
		cnt=0;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],a[i]);
		while(q--)
		{
			int l,r;scanf("%d%d",&l,&r);
			printf("%d\n",query(1,n,root[l-1],root[r],0));
		}
	}
    return 0;
}

详情