本文共 1196 字，大约阅读时间需要 3 分钟。

维护$n$颗$[1,i]$的权值线段树

然后对于每个询问$[l,r]$,可以利用主席树做差得到当前区间的值

又因为答案具有单调性,所以可以在树上二分得到解

#include 
   
    using namespace std;#define mid (l+r>>1)const int inf = 1e9;const int maxn = 1e6+10;const int N = maxn*40;int n,m,q,a[maxn];int sum[N],ls[N],rs[N],id,rt[N];void update(int &root,int pre,int l,int r,int val){
   	root = ++id;	ls[root] = ls[pre], rs[root] = rs[pre]; //sum[root] = sum[pre];	if( l==r )	{
    sum[root] = sum[pre]+1; return; }	if( val<=mid )	update( ls[root],ls[pre],l,mid,val );	else	update( rs[root],rs[pre],mid+1,r,val );	sum[root] = sum[ls[root]] + sum[rs[root]];}int ask(int &root,int pre,int l,int r,int val){
   	int x = sum[rs[root]] - sum[rs[pre]];//右子树的数量 	if( l==r )	return	l;                       	if( val+x>=mid+1 )	return ask( rs[root],rs[pre],mid+1,r,val );	else	return ask( ls[root],ls[pre],l,mid,val+x);}int main(){
   	while( cin >> n >> q )	{
   		for(int i=1;i<=n;i++)	cin >> a[i];		for(int i=1;i<=n;i++)//维护一颗[1,i]的线段树			update( rt[i],rt[i-1],0,inf,a[i] );		while( q-- )		{
   			int l,r; scanf("%d%d",&l,&r);			printf("%d\n",ask( rt[r],rt[l-1],0,inf,0 ) );		}		for(int i=0;i<=id;i++)			ls[i] = rs[i] = rt[i] = sum[i] = 0;		id = 0;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116501090 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！