可持久化数组
可以写一棵可持久化线段树，不过受到宇宙射线的影响，写了个奇奇怪怪的东西
因为是单点修改、单点查询，线段树只有叶子结点有用
中间结点没什么用还浪费空间，所以就不要中间结点了（大雾）
考虑建一棵树（大概类似平衡树？），维护左右儿子和权值，其他操作类似正常可持久化操作
\(build\)
奇奇怪怪的建树
il int build(cs int l,cs int r){
ri int mid=(l+r)>>1,rt=++id;
num[rt]=a[mid];
if(l^mid) ls[rt]=build(l,mid-1);
if(r^mid) rs[rt]=build(mid+1,r);
return rt;
}
\(update\)
可持久化部分，每次增加一条链
il int add(cs int o){
num[++id]=num[o];
ls[id]=ls[o],rs[id]=rs[o];
return id;
}
il void upd(int &rt,cs int k,cs int val){
ri int l=1,r=n,mid,i=rt=add(rt);
while(1){
mid=(l+r)>>1;
if(mid==k) {num[i]=val;break;}
if(mid<k) rs[i]=add(rs[i]),l=mid+1,i=id;
else ls[i]=add(ls[i]),r=mid-1,i=id;
}
}
\(ask\)
il int ask(ri int rt,cs int k){
ri int l=1,r=n,mid;
while(1){
mid=(l+r)>>1;
if(mid==k) return num[rt];
if(mid<k) l=mid+1,rt=rs[rt];
else r=mid-1,rt=ls[rt];
}
}
点击查看代码
#include <bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define F(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout);
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10|48),void();
}
il void wn(cs int x,cs char c=10){wt(x),putchar(c);}
} using namespace Q;
cs int N=1000005,LN=21000005;
int rot[N],a[N],n,m,id;
int num[LN],ls[LN],rs[LN];
il int build(cs int l,cs int r){
ri int mid=(l+r)>>1,rt=++id;
num[rt]=a[mid];
if(l^mid) ls[rt]=build(l,mid-1);
if(r^mid) rs[rt]=build(mid+1,r);
return rt;
}
il int add(cs int o){
num[++id]=num[o];
ls[id]=ls[o],rs[id]=rs[o];
return id;
}
il void upd(int &rt,cs int k,cs int val){
ri int l=1,r=n,mid,i=rt=add(rt);
while(1){
mid=(l+r)>>1;
if(mid==k) {num[i]=val;break;}
if(mid<k) rs[i]=add(rs[i]),l=mid+1,i=id;
else ls[i]=add(ls[i]),r=mid-1,i=id;
}
}
il int ask(ri int rt,cs int k){
ri int l=1,r=n,mid;
while(1){
mid=(l+r)>>1;
if(mid==k) return num[rt];
if(mid<k) l=mid+1,rt=rs[rt];
else r=mid-1,rt=ls[rt];
}
}
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=n;++i) a[i]=rd();
rot[0]=build(1,n);
for(ri int i=1,op,k;i<=m;++i){
rot[i]=rot[rd()],op=rd(),k=rd();
op&1?upd(rot[i],k,rd()):wn(ask(rot[i],k));
}
return 0;
}