大佬好强啊
by Programming_Konjac @ 2024-03-23 10:17:24
找到了，~~难以启齿的错~~
by cmrhhh @ 2024-03-23 12:22:48
AC代码，~~马蜂还行~~
```cpp
#include<iostream>
using namespace std;
const int MAXN=3.5e7+10;
int n,m,a[MAXN],vi,loci,opi,vali;
int tree_tot=0,root[MAXN];//root[i]为i版本的根编号，刚开始编号为0
struct Tree{
int l,r,val;
}tree[MAXN<<2];
int cpy(int id){
tree[++tree_tot]=tree[id];
return tree_tot;
}
int build(int id,int l,int r){
id=++tree_tot;
if(l==r){
tree[id].val=a[l];
return id;
}
int mid=l+r>>1;
tree[id].l=build(0,l,mid);
tree[id].r=build(0,mid+1,r);
return id;
}
int update(int id,int l,int r,int loc,int val){
id=cpy(id);
if(l==r)tree[id].val=val;
else {
int mid=l+r>>1;
if(mid>=loc)tree[id].l=update(tree[id].l,l,mid,loc,val);//等号记得带上
if(mid<loc) tree[id].r=update(tree[id].r,mid+1,r,loc,val);//左右儿子可能会改变
}
return id;
}
int query(int id,int l,int r,int loc){
if(l==r)return tree[id].val;
int mid=l+r>>1;
if(mid>=loc) return query(tree[id].l,l,mid,loc);
else return query(tree[id].r,mid+1,r,loc);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
root[0]=1;build(0,1,n);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&vi,&opi,&loci);
if(opi==1){
scanf("%d",&vali);
root[i]=update(root[vi],1,n,loci,vali);
}
if(opi==2){
printf("%d\n",query(root[vi],1,n,loci));
root[i]=root[vi];
}
}
return 0;
}
```
此帖结
by cmrhhh @ 2024-03-23 12:47:52