AC日记——[POI2014]KUR-Couriers 洛谷 P3567

[POI2014]KUR-Couriers

思路：

　　卡空间，sb题；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 500005

#define maxn_ maxn*19

int n,m,lc[maxn_],rc[maxn_],dis[maxn_],ans;

int ai[maxn],bi[maxn],root[maxn],tot,size;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void build(int &now,int l,int r)

{

    now=++tot;

    if(l==r) return;

    int mid=l+r>>;

    build(lc[now],l,mid);

    build(rc[now],mid+,r);

}

inline void add(int &now,int pre,int l,int r,int to)

{

    now=++tot,dis[now]=dis[pre]+;

    if(l==r) return;

    int mid=l+r>>;

    if(to<=mid) add(lc[now],lc[pre],l,mid,to),rc[now]=rc[pre];

    else add(rc[now],rc[pre],mid+,r,to),lc[now]=lc[pre];

}

inline void query(int now,int pre,int l,int r,int k)

{

    if(l==r) {ans=l;return;};

    int mid=l+r>>,di=dis[lc[now]]-dis[lc[pre]];

    if(di>=k) {query(lc[now],lc[pre],l,mid,k);return;}

    di=dis[rc[now]]-dis[rc[pre]];

    if(di>=k) {query(rc[now],rc[pre],mid+,r,k);return;}

    ans=;return;

}

int main()

{

    in(n),in(m);int l,r,to;

    for(int i=;i<=n;i++) in(ai[i]),bi[i]=ai[i];

    sort(bi+,bi+n+),size=unique(bi+,bi+n+)-bi-;

    build(root[],,size);

    for(int i=;i<=n;i++)

    {

        to=lower_bound(bi+,bi+size+,ai[i])-bi;

        add(root[i],root[i-],,size,to);

    }

    while(m--)

    {

        in(l),in(r);

        query(root[r],root[l-],,size,(r-l+>>)+);

        printf("%d\n",bi[ans]);

    }

    return ;

}