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

题目背景

这是个非常经典的主席树入门题——静态区间第

数据已经过加强，请使用主席树。同时请注意常数优化。

题目描述

如题，给定

输入格式

第一行包含两个整数，分别表示序列的长度 $a_iai。接下来 mm 行每行包含三个整数 l, r, kl,r,k , 表示查询区间 [l, r][l,r] 内的第 kk 小值。$

输出格式

对于每次询问，输出一行一个整数表示答案。

输入输出样例

输入 #1

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出 #1

说明/提示

样例 1 解释

$55，数列从第一项开始依次为\{25957, 6405, 15770, 26287, 26465\}{25957,6405,15770,26287,26465}。$

第一次查询为
第二次查询为
第三次查询为
第四次查询为
第五次查询为

数据规模与约定

对于 $20\%20% 的数据，满足 1 \leq n,m \leq 101≤n,m≤10。$
对于 $50\%50% 的数据，满足 1 \leq n,m \leq 10^31≤n,m≤103。$
对于 $80\%80% 的数据，满足 1 \leq n,m \leq 10^51≤n,m≤105。$
对于 $100\%100% 的数据，满足 1 \leq n,m \leq 2\times 10^51≤n,m≤2×105$

#include<iostream>
#include<algorithm>
using namespace std;
struct asd
{
    long long ls,rs;
    long long cnt;
} tr[4000001];
long long n,m,a[4000001],tot=0,root[4000001],b[4000001];
long long build(long long l,long long r)
{
    long long rt=++tot;
    long long mid=(l+r)/2;
    if(l!=r)
    {
        tr[rt].ls=build(l,mid);
        tr[rt].rs=build(mid+1,r);
    }
    return rt;
}
long long change(long long x,long long l,long long r,long long p)
{
    long long rt=++tot;
    tr[rt]=tr[p];
    tr[rt].cnt=tr[p].cnt+1;
    if(l==r) 
        return rt;
    long long mid=(l+r)/2;
    if(x<=mid)
        tr[rt].ls=change(x,l,mid,tr[p].ls);
    else
        tr[rt].rs=change(x,mid+1,r,tr[p].rs);
    return rt;
}
long long ask(long long p,long long q,long long l,long long r,long long k)
{
    if(l==r) return l;
    long long mid=(l+r)/2;
    long long lcnt=tr[tr[q].ls].cnt-tr[tr[p].ls].cnt;
    if(k<=lcnt) return ask(tr[p].ls,tr[q].ls,l,mid,k);
    else return ask(tr[p].rs,tr[q].rs,mid+1,r,k-lcnt);
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    long long q=unique(b+1,b+1+n)-b-1;
    root[0]=build(1,q);
    for(long long i=1;i<=n;i++)
    {
        long long t=lower_bound(b+1,b+1+q,a[i])-b;
        root[i]=change(t,1,q,root[i-1]);
    }
    long long l,r,k;
    for(long long i=1;i<=m;i++)
    {
        cin>>l>>r>>k;
        cout<<b[ask(root[l-1],root[r],1,q,k)]<<endl;
    }
    return 0;
}

可持久化线段树（主席树）