1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6+10;
int roots[maxN*30];
int cnt;
int A[maxN];
struct Tree{
struct Node{
int val;
int lson;
int rson;
Node(int val=0,int lson=0,int rson=0):val(val),lson(lson),rson(rson){};
}node[maxN*30];
void build(int &root,int l,int r){
root = ++cnt;
if(l == r){
node[root].val = A[l];
return;
}
int mid = (l + r) >> 1;
build(node[root].lson,l,mid);
build(node[root].rson,mid+1,r);
}
inline int clone(int k){
node[++cnt] = node[k];
return cnt;
}
int update(int root,int l,int r,int x,int val){
root = clone(root);
if(l == r){
node[root].val = val;
}else{
int mid = (l + r) >> 1;
if(x <= mid){
node[root].lson = update(node[root].lson,l,mid,x,val);
}else{
node[root].rson = update(node[root].rson,mid+1,r,x,val);
}
}
return root;
}
int Query(int root,int l,int r,int x){
if(l == r) return node[root].val;
int mid = (l + r) >> 1;
if(x <= mid) return Query(node[root].lson,l,mid,x);
else return Query(node[root].rson,mid+1,r,x);
}
}SegmentTree;
int main(){
int N,M;
scanf("%d%d",&N,&M);
for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
SegmentTree.build(roots[0],1,N);
for(int i = 1;i<=M;i++){
int v,opt,loc,val;
scanf("%d%d%d",&v,&opt,&loc);
if(opt & 1){
scanf("%d",&val);
roots[i] = SegmentTree.update(roots[v],1,N,loc,val);
}else{
int ans = SegmentTree.Query(roots[v],1,N,loc);
printf("%d\n",ans);
roots[i] = roots[v];
}
}
return 0;
}
|