Loading...

洛谷P3834 可持久化数组

check评论:0 条 remove_red_eye浏览量:464 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-29

qwq

刚复习完主席树,先把这道题秒了

我们对每次更新都新建一颗线段树,不过要利用之前的数据

然后就和主席树基本一样,查询就好qwq

code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
int sum[maxn<<5],l[maxn<<5],r[maxn<<5],val[maxn<<5],t[maxn],a[maxn],b[maxn];
int n,q,cnt;
int build(int lf,int rg)
{
    int rt=++cnt;
    if(lf==rg)
    {
        val[rt]=a[lf];
    }
    else
    {
        int mid=(lf+rg)>>1;
        l[rt]=build(lf,mid);
        r[rt]=build(mid+1,rg);
    }
    return rt;
}
int update(int ver,int lf,int rg,int pos,int t)
{
    int rt=++cnt;
    sum[rt]=sum[ver];
    l[rt]=l[ver];
    r[rt]=r[ver];
    if(lf==rg)
    {
        val[rt]=t;
    }
    else
    {
        int mid=(lf+rg)>>1;
        if(pos<=mid)
        {
            l[rt]=update(l[ver],lf,mid,pos,t);
        }
        else
        {
            r[rt]=update(r[ver],mid+1,rg,pos,t);
        }
    }
    return rt;
}
int query(int ver,int lf,int rg,int x)
{
    if(lf==rg)
    {
        return val[ver];        
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        return query(l[ver],lf,mid,x);
    }
    else
    {
        return query(r[ver],mid+1,rg,x);
    }
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    t[0]=build(1,n);
    for(int i=1;i<=q;i++)
    {
        int ver,opt,ls,rs;
        scanf("%d%d%d",&ver,&opt,&ls);
        if(opt==1)
        {
            scanf("%d",&rs);
            t[i]=update(t[ver],1,n,ls,rs);
        }
        else
        {
            printf("%d\n",query(t[ver],1,n,ls));
            t[i]=t[ver];
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名