可持久化数组-白红宇

可持久化数组

阅读量：4317 次

发布时间：2019-06-06

本文共 4352 字，大约阅读时间需要 14 分钟。

题目背景

UPDATE : 最后一个点时间空间已经放大

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

题目描述

如题，你需要维护这样的一个长度为

在某个历史版本上修改某一个位置上的值

访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入输出格式

输入格式：

输入的第一行包含两个正整数

第二行包含 $a_iai，1 \leq i \leq N1≤i≤N）。$

接下来

对于操作1，格式为 $v_i \ 1 \ {loc}_i \ {value}_ivi 1 loci valuei，即为在版本v_ivi的基础上，将 a_{$
{loc}_i} ${value}_ivaluei$

对于操作2，格式为 $v_i \ 2 \ {loc}_ivi 2 loci，即访问版本v_ivi中的 a_{ {loc}_i}aloci的值$

输出格式：

输出包含若干行，依次为每个操作2的结果。

输入输出样例

输入样例#1：

5 1059 46 14 87 410 2 10 1 1 140 1 1 570 1 1 884 2 40 2 50 2 44 2 12 2 21 1 5 91

输出样例#1：

598741878846

说明

数据规模：

对于30%的数据： $\leq N, M \leq {10}^31≤N,M≤103$

对于50%的数据： $\leq N, M \leq {10}^41≤N,M≤104$

对于70%的数据： $\leq N, M \leq {10}^51≤N,M≤105$

对于100%的数据： $\leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^91≤N,M≤106,1≤loci≤N,0≤vi<i,−109≤ai,valuei≤109$

代码

思路1：树上dfs离线操作

#include
     
      #define f(c)   for(int i=1;i<=c;i++)using namespace std;const int maxn = 1000009;int head[maxn],n,m,cnt,a[maxn],ans[maxn];struct edg{
   int next,to;}e[maxn];struct node{
   int ver,opt,pos,val;}q[maxn]; bool uuz[maxn];int I(){
   int x=0,f=1;char ch=getchar();    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}void add(int x,int y){e[++cnt].next=head[x];head[x]=cnt;e[cnt].to=y;}void dfs(int x){
   int last;    q[x].opt==1?last=a[q[x].pos],a[q[x].pos]=q[x].val:ans[x]=a[q[x].pos];    for(int i=head[x];i;i=e[i].next)dfs(e[i].to);    if(q[x].opt==1)a[q[x].pos]=last;}int main(){n=I();m=I();f(n)a[i]=I();    f(m){q[i].ver=I();q[i].opt=I();q[i].pos=I();        q[i].opt==1?q[i].val=I():uuz[i]=1;add(q[i].ver,i);}    dfs(0);f(m)if(uuz[i])printf("%d\n",ans[i]);return 0;}

思路2：可持久化线段树

#include
     
      #define f(a)  for(int i=1;i<=a;i++)const int N=1000005;using namespace std;int a[N],n,q,rt[N*20];int I(){
   int x=0,f=1;char ch=getchar();    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}struct Persistable_Segment_Tree{    int lc[N*20],rc[N*20],val[N*20],cnt;    inline void build(int &o,int l,int r){        o=++cnt;if(l==r){val[o]=a[l];return;}        int mid=(l+r)>>1;build(lc[o],l,mid);build(rc[o],mid+1,r);}    inline void ins(int &o,int pre,int l,int r,int q,int v){        o=++cnt;lc[o]=lc[pre];rc[o]=rc[pre];val[o]=val[pre];        if(l==r){val[o]=v;return;}int mid=(l+r)>>1;        q<=mid?ins(lc[o],lc[pre],l,mid,q,v):ins(rc[o],rc[pre],mid+1,r,q,v);}    inline int query(int o,int l,int r,int q){        if(l==r)return val[o];int mid=(l+r)>>1;        if(q<=mid)return query(lc[o],l,mid,q);        else return query(rc[o],mid+1,r,q);}}T;int main(){n=I();int m=I();f(n)a[i]=I();T.build(rt[0],1,n);    f(m){
    int pre=I(),opt=I(),x=I();        if(opt==1){
   int v=I();T.ins(rt[i],rt[pre],1,n,x,v);}       else printf("%d\n",T.query(rt[pre],1,n,x)),rt[i]=rt[pre];}}

思路3：主席树

#include
     
      using namespace std;#define MAX 1000100#define f(c)   for(int i=1;i<=c;i++)int I(){
   int x=0,f=1;char ch=getchar();    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}int root[MAX],a[MAX],N,M;struct Node{
   int l,r,ls,rs,val;}t[MAX*20];int sum=0,tot=1;void Build(int now,int l,int r){t[now].l=l;t[now].r=r;    if(l==r){t[now].val=a[l];return;}    t[now].ls=++tot;int mid=(l+r)>>1;    Build(tot,l,mid);t[now].rs=++tot;Build(tot,mid+1,r);}void AddNode(int now,int New,int k,int w){t[New]=t[now];    if(t[now].l==t[now].r){t[New].val=w;return;}    int mid=(t[now].l+t[now].r)>>1;    if(k<=mid)t[New].ls=++tot,AddNode(t[now].ls,tot,k,w);    else t[New].rs=++tot,AddNode(t[now].rs,tot,k,w);}void Query(int now,int k){    if(t[now].l==t[now].r){printf("%d\n",t[now].val);return;}    int mid=(t[now].l+t[now].r)>>1;    k<=mid?Query(t[now].ls,k):Query(t[now].rs,k);}int main(){N=I();M=I();f(N)a[i]=I();    Build(1,1,N);root[0]=1;    f(M){
    int v=I(),opt=I();        if(opt==1){
   int vv=I(),ww=I();AddNode(root[v],root[++sum]=++tot,vv,ww);}        else{
   int vv=I();Query(root[v],vv);root[++sum]=root[v];}}return 0;}

转载于:https://www.cnblogs.com/muzu/p/7898484.html

你可能感兴趣的文章