维护 n n n颗 [ 1 , i ] [1,i] [1,i]的权值线段树
然后对于每个询问 [ l , r ] [l,r] [l,r],可以利用主席树做差得到当前区间的值
又因为答案具有单调性,所以可以在树上二分得到解
#include <bits/stdc++.h>
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;
}
}