2023-07-23发表

可持久化线段树

题目背景

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

题目描述

如题，给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

输入格式

第一行包含两个整数，分别表示序列的长度 $n$ 和查询的个数 $m$。
第二行包含 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$。
接下来 $m$ 行每行包含三个整数 $ l, r, k$ , 表示查询区间 $[l, r]$ 内的第 $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

样例输出 #1

提示

样例 1 解释

$n=5$，数列长度为 $5$，数列从第一项开始依次为${25957, 6405, 15770, 26287, 26465}$。

第一次查询为 $[2, 2]$ 区间内的第一小值，即为 $6405$。
第二次查询为 $[3, 4]$ 区间内的第一小值，即为 $15770$。
第三次查询为 $[4, 5]$ 区间内的第一小值，即为 $26287$。
第四次查询为 $[1, 2]$ 区间内的第二小值，即为 $25957$。
第五次查询为 $[4, 4]$ 区间内的第一小值，即为 $26287$。

数据规模与约定

对于 $20%$ 的数据，满足 $1 \leq n,m \leq 10$。
对于 $50%$ 的数据，满足 $1 \leq n,m \leq 10^3$。
对于 $80%$ 的数据，满足 $1 \leq n,m \leq 10^5$。
对于 $100%$ 的数据，满足 $1 \leq n,m \leq 2\times 10^5$，$|a_i| \leq 10^9$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 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;
}

注意亿些细节：

数据规模：
1
2
3
4
5
6
struct node{
int lc;
int rc;
int val;
}tr[40000005];
int root[200005],val[200005];
初始简述需要开$2n-1$个节点。有$n$次插入，每次插入最多增加$\log n +1$个节点。
总共节点数为$n\log n+3n$,约为$20$倍;

查询

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);
 }

输出

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开始，
 }

#算法