luogu P3834 【模板】可持久化线段树 1（主席树）

题解真的是越写越懒

// luogu-judger-enable-o2

#include<cstdio>

#include<algorithm>

using std::sort;

const int maxn = 200006;

int n,m,sum[maxn<<5];

inline int read() {

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

int a[maxn],cnt,tot,root[maxn],hash[maxn],ls[maxn<<5],rs[maxn<<5];

void desk() {

    sort(hash+1,hash+n+1);

    cnt=std::unique(hash+1,hash+n+1)-(hash+1);

    for(int i=1;i<=n;i++) a[i]=std::lower_bound(hash+1,hash+cnt+1,a[i])-hash;

}

void insert(int l,int r,int &rt,int pre,int w) {

    rt=++tot;

    sum[rt]=sum[pre]+1;

    if(l==r)return;

    int mid=l+r>>1;

    if(w<=mid) rs[rt]=rs[pre],insert(l,mid,ls[rt],ls[pre],w);

    else ls[rt]=ls[pre],insert(mid+1,r,rs[rt],rs[pre],w);

}

int query(int l,int r,int tl,int tr,int k) {

    if(l==r)return l;

    int mid=l+r>>1,tmp=sum[ls[tr]]-sum[ls[tl]];

    if(tmp>=k)return query(l,mid,ls[tl],ls[tr],k);

    else return query(mid+1,r,rs[tl],rs[tr],k-tmp);

}

int main() {

    n=read(),m=read();

    for(int i=1;i<=n;++i) a[i]=read(),hash[i]=a[i];

    desk();

    for(int i=1;i<=n;++i) insert(1,cnt,root[i],root[i-1],a[i]);

    for(int l, r, k;m--;) {

        l=read(),r=read(),k=read();

        printf("%d\n",hash[query(1,cnt,root[l-1],root[r],k)]);

    }

    return 0;

}

巴特西

luogu P3834 【模板】可持久化线段树 1（主席树）

最新文章

热门文章