Loading...

[可持久化线段树]主席树 洛谷P3834

check评论:1 条 remove_red_eye浏览量:650 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-06-07

主席树,顾名思义主席的树,是利用函数式的编程思想使得线段树支持查询历史版本,同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构。一棵线段树的节点维护的是当前节点对应的区间信息,若每次区间不同则处理较为困难,例如频繁的询问区间第K大元素(较为简单的思想是根据归并排序思想实现的归并树,但是时空复杂度都较高)
这里挂一个很好的博客,可以去上面看详解
code:

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=200001;
#define mid ((lf+rg)>>1)
int n,q,m,cnt=0;
int a[maxn],b[maxn],t[maxn];
int sum[maxn<<5],l[maxn<<5],r[maxn<<5];
int build(int lf,int rg)
{
    int rt=++cnt;
    sum[rt]=0;
    if(lf<rg)
    {
        l[rt]=build(lf,mid);
        r[rt]=build(mid+1,rg);
    }
    return rt;
}
int update(int pre,int lf,int rg,int x)
{
    int rt=++cnt;
    l[rt]=l[pre];
    r[rt]=r[pre];
    sum[rt]=sum[pre]+1;
    if(lf<rg)
    {
        if(x<=mid)
        {
            l[rt]=update(l[pre],lf,mid,x);
        }
        else
        {
            r[rt]=update(r[pre],mid+1,rg,x);
        }
    }
    return rt;
}
int query(int u,int v,int lf,int rg,int k)
{
    if(lf>=rg)
    {
        return lf;
    }
    int x=sum[l[v]]-sum[l[u]];
    if(x>=k)
    {
        return query(l[u],l[v],lf,mid,k);
    }
    else
    {
        return query(r[u],r[v],mid+1,rg,k-x);
    }
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    t[0]=build(1,m);
    for(int i=1;i<=n;i++)
    {
        int tq=lower_bound(b+1,b+1+m,a[i])-b;
        t[i]=update(t[i-1],1,m,tq);
    } 
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        int tq=query(t[x-1],t[y],1,m,z);
        printf("%d\n",b[tq]);
    }
    return 0;
}

NOIP2018游记 chevron_right

仅有一条评论

正在回复给  
去登陆?

   点击刷新验证码

    smy
    2018 - 06 - 12 16 : 14

    主席树不是一个姓黄名jt的人提出的吗qwq

标签云

文章留名

smy
smy