Warning: session_start(): open(/tmp/sess_c3624966829325a077f54691c9535775, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 可持久化数组 ======
===== 例题 =====
[[https://www.luogu.com.cn/problem/P3919|洛谷 P3919 【模板】可持久化线段树 1（可持久化数组）]]
参考代码：
#include
using namespace std;
const int N=1e6+5;
int a[N];
int rt[N*20],ls[N*20],rs[N*20],tr[N*20],cnt;
void build(int& o,int l,int r){
o=++cnt;
if(l==r){
tr[o]=a[l];
return;
}
int mid=l+r>>1;
build(ls[o],l,mid);
build(rs[o],mid+1,r);
}
void xg(int& o,int l,int r,int pre,int pos,int v){
o=++cnt;
ls[o]=ls[pre];
rs[o]=rs[pre];
tr[o]=tr[pre];
if(l==r){
tr[o]=v;
return;
}
int mid=l+r>>1;
if(pos<=mid) xg(ls[o],l,mid,ls[pre],pos,v);
if(pos>mid) xg(rs[o],mid+1,r,rs[pre],pos,v);
}
int cx(int o,int l,int r,int pos){
if(l==r) return tr[o];
int mid=l+r>>1;
if(pos<=mid) return cx(ls[o],l,mid,pos);
if(pos>mid) return cx(rs[o],mid+1,r,pos);
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(rt[0],1,n);
for(int i=1;i<=m;i++){
int pre,op,pos;
scanf("%d %d %d",&pre,&op,&pos);
if(op==1){
int v;
scanf("%d",&v);
xg(rt[i],1,n,rt[pre],pos,v);
}
else{
printf("%d\n",cx(rt[pre],1,n,pos));
rt[i]=rt[pre];
}
}
}