【洛谷P3834】【模板】可持久化线段树1

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P3834
静态区间第$k$k小。
给定$N$N个整数构成的序列，将对于指定的闭区间查询其区间内的第$K$K小值。

---

思路：

主席树模板题。没什么好讲的。。。

---

代码：

#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

const int M=3800010;
const int N=200010;
int n,m,x,y,z,T,tot,a[N],b[N],root[N];

struct Tree
{
    int ls,rs,cnt;
}tree[M];

int build(int l,int r)
{
    int p=++tot;
    if (l==r) return p;
    int mid=(l+r)/2;
    tree[p].ls=build(l,mid);
    tree[p].rs=build(mid+1,r);
    return p;
}

int insert(int now,int l,int r,int k)
{
    int p=++tot;
    tree[p]=tree[now];
    tree[p].cnt++;
    if (l==r) return p;
    int mid=(l+r)/2;
    if (k<=mid) tree[p].ls=insert(tree[p].ls,l,mid,k);
        else tree[p].rs=insert(tree[p].rs,mid+1,r,k);
    return p;
}

int ask(int x,int y,int l,int r,int k)
{
    if (l==r) return l;
    int mid=(l+r)/2,sum=tree[tree[y].ls].cnt-tree[tree[x].ls].cnt;
    if (sum>=k)
        return ask(tree[x].ls,tree[y].ls,l,mid,k);
    else return ask(tree[x].rs,tree[y].rs,mid+1,r,k-sum);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n); 
    T=unique(b+1,b+1+n)-b-1;
    root[0]=build(1,T);
    for (int i=1;i<=n;i++)
        root[i]=insert(root[i-1],1,T,lower_bound(b+1,b+1+T,a[i])-b);
    while (m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",b[ask(root[x-1],root[y],1,T,z)]);
    }
    return 0;
}