Steven_MengのBlog

传送门

用可持久化线段树实现,$rt[i]$表示每个副本线段树的根节点。

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define MAXM 30
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN];
namespace SegmentTree{
struct node{
int l,r;
int val;//每个节点的权值(只有叶节点有)
}tree[MAXN*MAXM];
int tot;
void Build(int &i,int L,int R){
i=++tot;
if (L==R){
tree[i].val=a[L];
return ;
}
int mid=(L+R)>>1;
Build(tree[i].l,L,mid);
Build(tree[i].r,mid+1,R);
}
void Update(int &i,int his,int pos,int val,int L,int R){
i=++tot;
tree[i].l=tree[his].l,tree[i].r=tree[his].r,tree[i].val=tree[his].val;
if (L==R){
tree[i].val=val;
return ;
}
int mid=(L+R)>>1;
if (pos<=mid) Update(tree[i].l,tree[his].l,pos,val,L,mid);
else Update(tree[i].r,tree[his].r,pos,val,mid+1,R);
}
int Query(int i,int pos,int L,int R){
if (L==R) return tree[i].val;
int mid=(L+R)>>1;
if (pos<=mid) return Query(tree[i].l,pos,L,mid);
else return Query(tree[i].r,pos,mid+1,R);
}
}
using namespace SegmentTree;
int rt[MAXN];
int main(){
int n=read(),q=read();
for (register int i=1;i<=n;++i) a[i]=read();
Build(rt[0],1,n);
for (register int i=1;i<=q;++i){
int v=read(),opr=read(),loc=read();
if (opr==1){
int val=read();
Update(rt[i],rt[v],loc,val,1,n);
}
else if (opr==2){
printf("%d\n",Query(rt[v],loc,1,n));
rt[i]=rt[v];
}
}
}

 评论