这题好水的说~很明显就是主席树的大板子
然而我交了3遍才调完所有的BUG，开好足够的数组，卡掉大大的常数；
针对与每次操作，change()会创建新节点,而ask()虽然也会更新左右儿子的节点编号，但并不会创建除根节点以外的点；
处理好以上change()和ask()的细节就可以轻松地切掉这道题；
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
int n,m;
int a[];
int cnt;
int b[];
int L[];
int R[];
int root[];
int build(int l,int r)
{
int rt=++cnt;
if(l==r){
a[rt]=b[l];
return rt;
}
L[rt]=build(l,mid);
R[rt]=build(mid+,r);
return rt;
}
int change(int vpre,int vnow,int l,int r,int x,int value)
{
int rt=++cnt;
if(l==r){
if(l==x){
a[rt]=value;
}
return rt;
}
L[rt]=L[vpre];
R[rt]=R[vpre];
if(mid>=x){
L[rt]=change(L[vpre],rt,l,mid,x,value);
}
else{
R[rt]=change(R[vpre],rt,mid+,r,x,value);
}
return rt;
}
int ask(int vpre,int vnow,int l,int r,int x)
{
L[vnow]=L[vpre];
R[vnow]=R[vpre];
if(l==r){
if(l==x){
cout<<a[vnow]<<endl;
}
return vnow;
}
if(x<=mid) L[vnow]=ask(L[vpre],L[vnow],l,mid,x);
else R[vnow]=ask(R[vpre],R[vnow],mid+,r,x);
return vnow;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&b[i]);
}
root[]=build(,n);
for(int i=;i<=m;i++){
int v,opt;
scanf("%d%d",&v,&opt);
if(opt==){
int weizhi,value;
scanf("%d%d",&weizhi,&value);
root[i]=change(root[v],cnt+,,n,weizhi,value);
}
else{
int weizhi;
scanf("%d",&weizhi);
root[i]=++cnt;
ask(root[v],cnt,,n,weizhi);
}
}
}