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

传送门
题目背景
这是个非常经典的主席树入门题——静态区间第K小

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

题目描述
如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入格式
第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个整数，表示这个序列各项的数字。

接下来M行每行包含三个整数 l, r, kl,r,k , 表示查询区间[l, r][l,r]内的第k小值。

输出格式
输出包含k行，每行1个整数，依次表示每一次查询的结果

输入输出样例

输入 #1 复制
5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

数据范围：

对于20%的数据满足： 1 \leq N, M \leq 101≤N,M≤10

对于50%的数据满足： 1 \leq N, M \leq 10^31≤N,M≤103

对于80%的数据满足： 1 \leq N, M \leq 10^51≤N,M≤105

对于100%的数据满足： 1 \leq N, M \leq 2\cdot 10^51≤N,M≤2⋅105

对于数列中的所有数 a_iai ，均满足 -{10}^9 \leq a_i \leq {10}^9−109≤ai≤109

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为 [25957, 6405, 15770, 26287, 26465 ][25957,6405,15770,26287,26465]

第一次查询为 [2, 2][2,2] 区间内的第一小值，即为6405

第二次查询为 [3, 4][3,4] 区间内的第一小值，即为15770

第三次查询为 [4, 5][4,5] 区间内的第一小值，即为26287

第四次查询为 [1, 2][1,2] 区间内的第二小值，即为25957

第五次查询为 [4, 4][4,4] 区间内的第一小值，即为26287

这题是个主席树入门题，如题目可持久化线段树，也是主席树板子题；

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int MM=200010;
int node,n,m;
int sum[MM*5],rt[MM],lc[MM*5],rc[MM*5];
int a[MM],b[MM];
int p;
void build(int &t,int l,int r)//建树
{
    t=++node;
    if(l==r)
        return;
    int mid=((l+r)>>1);
    build(lc[t],l,mid);
    build(rc[t],mid+1,r);
}
int update(int o,int l,int r)//更新
{
    int rt=++node;
    lc[rt]=lc[o];
    rc[rt]=rc[o];
    sum[rt]=sum[o]+1;
    if(l==r)
        return rt;
    int mid=((l+r)>>1);
    if(p<=mid)
        lc[rt]=update(lc[rt],l,mid);
    else
        rc[rt]=update(rc[rt],mid+1,r);
    return rt;
}
int query(int u,int v,int l,int r,int k)//查询
{
    int ans,mid=((l+r)>>1),x=sum[lc[v]]-sum[lc[u]];//前缀和
    if(l==r)
        return l;
    if(x>=k)//说明在左子树
        ans=query(lc[u],lc[v],l,mid,k);//
    else
        ans=query(rc[u],rc[v],mid+1,r,k-x);
    return ans;
}
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+n+1);//离散化
    int q=unique(b+1,b+n+1)-b-1;//
    build(rt[0],1,q);
    for(register int i=1; i<=n; i++)
    {
        p=lower_bound(b+1,b+q+1,a[i])-b;//二分
        rt[i]=rt[i-1];
        rt[i]=update(rt[i],1,q);
    }
    int l,r,k,ans;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        ans=query(rt[l-1],rt[r],1,q,k);
        printf("%d\n",b[ans]);
    }
    return 0;
}

看了这个对于里面出现的register和unique不了解的同学可以看here
当然还可以用一个简单的板子

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn =200010;
int n, m;
int cnt;
struct node//存树
{
    int L, R;//分别指向左右子树
    int sum;//该节点所管辖区间范围内数的个数
}Tree[maxn * 20];
struct value//值 //离散化
{
    int x;//值的大小
    int id;//离散之前在原数组中的位置
} Value[maxn];
bool cmp(value v1, value v2)//排序从到小
{
    return v1.x < v2.x;
}
int root[maxn];//多颗线段树的根节点
int yy[maxn];//原数组离散之后的数组
void update(int num, int &rt, int l, int r)
{
    Tree[cnt++] = Tree[rt];
    rt = cnt - 1;
    Tree[rt].sum++;
    if(l == r) return;
    int mid = (l + r)>>1;
    if(num <= mid)
        update(num,Tree[rt].L,l,mid);
    else
        update(num,Tree[rt].R,mid+1,r);
}
int query(int i,int j,int k,int l,int r)
{
    int d=Tree[Tree[j].L].sum-Tree[Tree[i].L].sum;
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(k<=d)
        return query(Tree[i].L,Tree[j].L,k,l,mid);
    else return query(Tree[i].R, Tree[j].R,k-d,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&Value[i].x);
        Value[i].id=i;
    }
    //进行离散化
    sort(Value + 1,Value+n+1, cmp);
    for(int i=1; i<=n; i++)
    {
        yy[Value[i].id]=i;
    }
//    init();//初始化
    cnt=1;
    for(int i=1; i<=n; i++)
    {
        root[i]=root[i - 1];
        update(yy[i],root[i],1,n);
    }
    int left, right,k;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &left, &right, &k);
        printf("%d\n", Value[query(root[left - 1], root[right], k, 1, n)].x);
    }
    return 0;
}