欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷.3834.[模板]可持久化线段树(主席树 静态区间第k小)

程序员文章站 2024-03-04 12:18:05
...

题目链接

//离散化后范围1~cnt不要错 
#include<cstdio>
#include<cctype>
#include<algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e5+5,MAXIN=2e6;

int n,m,A[N],ref[N],cnt,sum[N*18],tot,son[N*18][2],root[N];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
    int now=0,f=1;register char c=gc();
    for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;
}

int Find(int v)
{
    int l=1,r=cnt,m;
    while(l<r)
        if(ref[m=l+r>>1]<v) l=m+1;
        else r=m;
    return l;
}
void Discrete()
{
    std::sort(ref+1,ref+1+n);
    cnt=1;
    for(int i=2;i<=n;++i)
        if(ref[i]!=ref[i-1]) ref[++cnt]=ref[i];
    for(int i=1;i<=n;++i) A[i]=Find(A[i]);
}
void Build(int x,int &y,int l,int r,int pos)
{
    sum[y=++tot]=sum[x]+1;
    if(l==r) return;
    int m=l+r>>1;
    if(pos<=m) son[y][1]=son[x][1],Build(son[x][0],son[y][0],l,m,pos);
    else son[y][0]=son[x][0],Build(son[x][1],son[y][1],m+1,r,pos);
}
int Query(int x,int y,int l,int r,int k)
{
    if(l==r) return l;
    int m=l+r>>1,tmp=sum[son[y][0]]-sum[son[x][0]];
    if(tmp>=k) return Query(son[x][0],son[y][0],l,m,k);
    else return Query(son[x][1],son[y][1],m+1,r,k-tmp);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("3834.in","r",stdin);
#endif

    n=read(),m=read();
    for(int i=1;i<=n;++i) ref[i]=A[i]=read();
    Discrete();
    for(int i=1;i<=n;++i) Build(root[i-1],root[i],1,cnt,A[i]);
    for(int i=1,l,r,k;i<=m;++i)
        l=read(),r=read(),k=read(),printf("%d\n",ref[Query(root[l-1],root[r],1,cnt,k)]);

    return 0;
}