C62 可持久化线段树 P3567 [POI2014] KUR-Couriers

#include<bits/stdc++.h>
using namespace std;
#define lc(x) tr[x].ls
#define rc(x) tr[x].rs
#define mid (l+r)/2
const int N=5e5+10;
struct trnode{int ls,rs,siz;}tr[N*40]; int trlen,rt[N],a[N];
void change(int pre,int &now,int l,int r,int x)
{
	now=++trlen;tr[now]=tr[pre];
    tr[now].siz++;
	if(l==r){return ;}
	if(x<=mid) change(lc(pre),lc(now),l,mid,x);
	else       change(rc(pre),rc(now),mid+1,r,x);
}
int query(int pre,int now,int l,int r,int k)
{
    if(l==r) return l;
    int s1=tr[lc(now)].siz-tr[lc(pre)].siz;
    int s2=tr[rc(now)].siz-tr[rc(pre)].siz;
    if(k<=s1) return query(lc(pre),lc(now), l, mid, k);
    if(k<=s2) return query(rc(pre),rc(now), mid+1, r, k);
    return 0;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    trlen=0;rt[0]=0;
    for(int i=1; i<=n; i++) change(rt[i-1],rt[i],1,n,a[i]);
    for(int i=1,x,y; i<=m; i++)
    {
        scanf("%d%d",&x,&y);if(x>y)swap(x,y);
        printf("%d\n", query(rt[x-1],rt[y],1,n,(y-x+1)/2+1));
    }
    return 0;
}