AcWing 255. 第K小数（主席树写法）

2021-01-14 14:14

阅读：537

标签：uil 离散化节点 return using sed out mat ras

区间k小数是主席树的模板题目，如果区间不包含，用莫队+权值线段树也能解

主席树是可持久化线段树，所为可持久化，就是每次只新增不一样的节点，而保留前面的版本，这样可以做到查询。

如果询问时1-r，那么直接主席树，询问的是l-r，就用到前缀和思想，具体看代码注释

#include
#include
#include
#include
#include
#includestring>
#include
#includeusing namespace std;
typedef long long ll;
const int N=3e5+10;
vectorint> num;
int a[N];
int root[N];
int idx;
struct node{  //左儿子，右儿子，个数 
    int l,r;
    int cnt; 
}tr[N*4+N*17];  //注意大小 
int find(int x){  //离散化后二分查找，+1是因为我习惯从1-n建树，不+1就是0-n-1建树，是一样的 
    return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
int build(int l,int r){ //初始建树操作，其实没有必要 
    int q=++idx;   
    if(l==r){
        return q;
    }
    int mid=l+r>>1;
    tr[q].l=build(l,mid); 
    tr[q].r=build(mid+1,r);
    return q;
}
int insert(int p,int l,int r,int x){
    int q=++idx;//为新节点开辟空间 
    tr[q]=tr[p];//持久化的原理，先复制前面一版的信息 
    if(l==r){
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(xmid)
    tr[q].l=insert(tr[p].l,l,mid,x);//如果在左儿子改变，与前一版本的区别就是左儿子 
    else
    tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].r].cnt+tr[tr[q].l].cnt; //记得更新区间的个数 
    return q; 
}
int query(int p,int q,int l,int r,int k){
    if(l==r){
        return l;
    }
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;  //前缀和思想，l-r其实就是r版本-l-1版本的个数 
    int mid=l+r>>1;
    if(kcnt)
    return query(tr[p].l,tr[q].l,l,mid,k);
    else
    return query(tr[p].r,tr[q].r,mid+1,r,k-cnt); //k-cnt是减去左节点的个数 
}
int main(){
    int i;
    int n;
    int m;
    cin>>n>>m;
    for(i=1;i){
        cin>>a[i];
        num.push_back(a[i]);
    }
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end()); //离散化 
    root[0]=build(1,num.size());
    for(i=1;i){
        root[i]=insert(root[i-1],1,num.size(),find(a[i]));
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout1],root[r],1,num.size(),k)-1]endl;
    }
}

View Code

AcWing 255. 第K小数（主席树写法）

标签：uil 离散化节点 return using sed out mat ras

原文地址：https://www.cnblogs.com/ctyakwf/p/12256624.html

上一篇：C#如何优雅地取消一个流程（非Thread.Abort方法）

下一篇：winform控件的二次开发

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 255. 第K小数（主席树写法）
文章链接：http://soscw.com/index.php/essay/41819.html

亲，登录后才可以留言！

AcWing 255. 第K小数（主席树写法）

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 255. 第K小数 （主席树写法）

评论

热门文章

推荐文章

最新文章

置顶文章

AcWing 255. 第K小数（主席树写法）