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

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

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>

#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=500007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

template<typename T>void read(T &x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x*=f;
}

int n,m,q,cnt;
int a[N],b[N],T[N];
int sum[N<<5],L[N<<5],R[N<<5];

inline void build(int &t,int l,int r)//直接用引用变量&t
{
    int rt=++cnt;//rt是当前节点的编号
    sum[rt]=0;//初始化
    if(l==r)return;
    build(L[rt],l,mid);
    build(R[rt],mid+1,r);
}

inline int update(int p,int l,int r,int x)//p为旧树该位置节点的编号
{
    int rt=++cnt;//新建节点的编号
    L[rt]=L[p];
    R[rt]=R[p];//该节点左右儿子初始化为旧树该位置节点的左右儿子
    sum[rt]=sum[p]+1;//因为插入的a[i](或b[x])在该节点所代表的区间中 所以sum++
    if(l!=r)
    {
        if(x<=mid)L[rt]=update(L[p],l,mid,x);
        //x出现在左子树 因此右子树保持与旧树相同 修改左子树
        else R[rt]=update(R[p],mid+1,r,x);
    }
    return rt;
}

inline int query(int u,int v,int l,int r,int k)
{
    if(l==r)return b[l];
    int num=sum[L[v]]-sum[L[u]];
    if(num>=k)return query(L[u],L[v],l,mid,k);
    else return query(R[u],R[v],mid+1,r,k-num);
}
int sizes;
int main()
{
    read(n),read(m);
    over(i,1,n)
    read(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    sizes=unique(b+1,b+1+n)-b-1;
    //size为线段树维护的数组的大小==b数组中不重复的数字的个数
    build(T[0],1,sizes); //初始化 建立一颗空树 并把该树的根节点的编号赋值给T[0]
    over(i,1,n)
    {
        int t=lower_bound(b+1,b+1+sizes,a[i])-b;
        T[i]=update(T[i-1],1,sizes,t);
    }
    //cout<<"123"<<endl;
    while(m--)
    {
        int l,r,k;
        read(l),read(r),read(k);
        printf("%d\n",query(T[l-1],T[r],1,sizes,k));
    }
    return 0;
}