题目
传送门：QWQ
传送到洛谷QWQ
分析
把求区间第k大的改一改就ok了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=;
int root[N*], ls[N*], rs[N*], sum[N*];
int n, m, newp; void add(int l,int r,int x,int& cur,int cur1)
{
cur=++newp;
ls[cur]=ls[cur1]; rs[cur]=rs[cur1]; sum[cur]=sum[cur1]+;
if(l==r) return; int mid=l+r>>;
if(x<=mid) add(l,mid,x,ls[cur],ls[cur1]);
else add(mid+,r,x,rs[cur],rs[cur1]);
} int query(int l,int r,int k,int cur,int cur1)
{
if(l==r) return l;
int mid=l+r>>, cmp1=sum[ls[cur1]]-sum[ls[cur]], cmp2=sum[rs[cur1]]-sum[rs[cur]];
if(cmp1>k) return query(l,mid,k,ls[cur],ls[cur1]);
else if(cmp2>k) return query(mid+,r,k,rs[cur],rs[cur1]);
return ;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
int x; scanf("%d",&x);
add(,n,x,root[i],root[i-]);
} for(int i=;i<=m;i++)
{
int l,r; scanf("%d%d",&l,&r);
printf("%d\n",query(,n,r-l+>>,root[l-],root[r]));
}
return ;
}