题目链接
如题，你需要维护这样的一个长度为 N 的数组，支持如下两种操作：
- 在某个历史版本上修改某一个位置上的值。
- 访问某个历史版本上的某一位置的值。
此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）。
对于操作 2，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。
对于 100% 的数据：
- 1 <= N, M <= 10^6；
- 1 <= p <= N；
- 设当前是第 x 次操作，0 <= v < x；
- -10^9 <= a_i,c <= 10^9。
本题是正常线段树+可持久化
const int N = 1e6+2;
int n,m,a[N];
struct node{int l,r,val;
}hjt[N*40];
int cnt,root[N];
void build(int l,int r,int &now){now=++cnt;if(l==r){hjt[now].val=a[l];return;}int m=(l+r)>>1;build(l,m,hjt[now].l);build(m+1,r,hjt[now].r);
}
//main函数内部
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>a[i];
}
build(1,n,root[0]);
先初始化，开始建树，建树过程与正常线段树区别不大
void modify(int l,int r,int ver,int &now,int &pos,int &num){hjt[now=++cnt]=hjt[ver];if(l==r){hjt[now].val=num;return;}int mid=(l+r)>>1;if(pos<=mid)modify(l,mid,hjt[ver].l,hjt[now].l,pos,num);else modify(mid+1,r,hjt[ver].r,hjt[now].r,pos,num);
}
int query(int l,int r,int now,int &pos){if(l==r){return hjt[now].val;}int mid=(l+r)>>1;if(pos<=mid)return query(l,mid,hjt[now].l,pos);else return query(mid+1,r,hjt[now].r,pos);
}
//main函数内部
for(int i=1;i<=m;i++){int v,opt,x,y;cin>>v>>opt;switch(opt){case 1:cin>>x>>y;modify(1,n,root[v],root[i],x,y);break;case 2:cin>>x;cout<<query(1,n,root[v],x)<<"\n";root[i]=root[v];break;}
}
modify()与可持久化线段树/主席树的modify()函数类似，先复制前一个版本，后续逐个修改不一样的节点
query()与正常线段树查询类似
main()函数只需要判断opt然后接着调用即可