可持久化线段树

题目背景#

这是个非常经典的可持久化权值线段树入门题——静态区间第小。

题目描述#

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

输入格式#

第一行包含两个整数，分别表示序列的长度和查询的个数。
第二行包含个整数，第个整数表示序列的第个元素。
接下来行每行包含三个整数 , 表示查询区间内的第小值。

输出格式#

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

样例 #1#

样例输入 #1#

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

plaintext

样例输出 #1#

plaintext

提示#

样例 1 解释#

，数列长度为，数列从第一项开始依次为。

第一次查询为区间内的第一小值，即为。
第二次查询为区间内的第一小值，即为。
第三次查询为区间内的第一小值，即为。
第四次查询为区间内的第二小值，即为。
第五次查询为区间内的第一小值，即为。

数据规模与约定#

对于的数据，满足。
对于的数据，满足。
对于的数据，满足。
对于的数据，满足，，，。

AC Code#

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;}
struct node{
    int lc;
    int rc;
    int val;
}tr[40000005];
int root[200005],val[200005];
int idx=0,n,m,maxn;
vector<int>a;
void build(int &pos,int l,int r){
    pos=++idx;
    if(l==r) return;
    int mid = (l+r)>>1;
    build(tr[pos].lc,l,mid);build(tr[pos].rc,mid+1,r);
}
void insert(int pre,int &pos,int l,int r,int val){
    pos=++idx;tr[pos]=tr[pre];tr[pos].val++;
    if(l==r)return;
    int mid = (l+r)>>1;
    if(mid>=val)insert(tr[pre].lc,tr[pos].lc,l,mid,val);
    else insert(tr[pre].rc,tr[pos].rc,mid+1,r,val);
}
int query(int l_pos,int r_pos,int l,int r,int rank){
    if(l==r)return l;
    int mid = (l+r)>>1;
    int s = tr[tr[r_pos].lc].val-tr[tr[l_pos].lc].val;
    if(s>=rank) return query(tr[l_pos].lc,tr[r_pos].lc,l,mid,rank);
    else return query(tr[l_pos].rc,tr[r_pos].rc,mid+1,r,rank-s);
}
int getid(int val){
    return lower_bound(a.begin(),a.end(),val)-a.begin()+1;
}
int main(){
    n=read(),m=read();
    for(int i = 1;i<=n;i++){
        val[i]=read();
        a.push_back(val[i]);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    maxn=a.size();
    build(root[0],1,maxn);
    for(int i = 1;i<=n;i++){
        insert(root[i-1],root[i],1,maxn,getid(val[i]));
    }
    for(int i = 1,x,y,z;i<=n;i++){
        x=read(),y=read(),z=read();
        cout<<a[query(root[x-1],root[y],1,maxn,z)-1]<<endl;
    }
    return 0;
}

cpp

注意亿些细节：

数据规模：
```
struct node{
     int lc;
     int rc;
     int val;
 }tr[40000005];
 int root[200005],val[200005];
```
cpp
初始简述需要开个节点。有次插入，每次插入最多增加个节点。总共节点数为,约为倍;

查询

int query(int l_pos,int r_pos,int l,int r,int rank){
     if(l==r)return l;
     int mid = (l+r)>>1;
     int s = tr[tr[r_pos].lc].val-tr[tr[l_pos].lc].val;//要判断是当前节点左儿子的情况
     if(s>=rank) return query(tr[l_pos].lc,tr[r_pos].lc,l,mid,rank);
     else return query(tr[l_pos].rc,tr[r_pos].rc,mid+1,r,rank-s);
 }

cpp

输出

for(int i = 1,x,y,z;i<=n;i++){
     x=read(),y=read(),z=read();
     cout<<a[query(root[x-1],root[y],1,maxn,z)-1]<<endl;//是x,y所在版本的根导入函数，由于vector a数据从0开始，
 }

cpp