可持久化线段树(主席树) - AcWing - 255 - 第k小数

update 2020-12-28
推荐一种非常好看的写法良心的可持久化线段树教程

1. 本题思路: 对于询问,利用主席树处理右端点,利用两个版本的线段树作差解决左端点.
2. 本题代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+50;

int len;
int n,m;
int a,b,c;
int idx;        // 索引分配器
int tree[N<<5];    // 
int lson[N<<5];    // 根索引 -> 左子索引
int rson[N<<5];    // 根索引 -> 右子索引
int roots[N];    // 版本号 -> 根索引
int arr[N]; // 原数列
int newarr[N]; // 有序数列
void build(int l,int r,int &rt){ // 建立空树
    rt = ++idx;
    if(l==r)return;
    int mid = l+r>>1;
    build(l,mid,lson[rt]);
    build(mid+1,r,rson[rt]);
}


void update(int l,int r,int oldRoot,int &newRoot,int pos){     //单点修改
    newRoot = ++idx;
    tree[newRoot] = tree[oldRoot] + 1;
    if(l == r){
        return;
    }

    int mid = l+r>>1;
    if(pos <= mid){
        rson[newRoot] = rson[oldRoot];
        update(l,mid,lson[oldRoot],lson[newRoot],pos);
    }else{
        lson[newRoot] = lson[oldRoot];
        update(mid+1,r,rson[oldRoot],rson[newRoot],pos);
    }
    // 对于本题,可以不push_up,直接修改 
}   

int query(int l,int r,int lrt,int rrt,int k){ // 传入 root[l-1], root[r]
    if(l==r)return l;
    int mid = l+r>>1;
    if(k <= tree[lson[rrt]] - tree[lson[lrt]]){
        return query(l,mid,lson[lrt],lson[rrt],k);
    }else{
        return query(mid+1,r,rson[lrt],rson[rrt],k-tree[lson[rrt]]+tree[lson[lrt]]);
    }
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d",&arr[i]);
        newarr[i] = arr[i];
    }

    sort(newarr+1,newarr+1+n);
    len = unique(newarr+1,newarr+1+n) - (newarr+1);

    build(1,len,roots[0]);

    for(int i = 1; i <= n; i++){
        int x = lower_bound(newarr+1,newarr+1+len,arr[i]) - newarr;
        update(1,len,roots[i-1],roots[i],x);
    }
    
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d",&a,&b,&c);
        printf("%d\n",newarr[query(1,len,roots[a-1],roots[b],c)]);
    }

    system("pause");
    return 0;
}

3. 一点感想: 看了清北选手的博客,感触挺大. 一方面非常佩服,一方面非常羡慕. 后悔自己从小到大都是玩过来的,只在高三拼了一把,高考还考的挺差. 怪自己. 另外要是原来早点接触OI就好了呀.感觉这些东西比物理化学那些东西有趣多了. 最后,希望自己能好好提升自己.研究生能上清北吧.

可持久化线段树(主席树) - AcWing - 255 - 第k小数