用可持久化线段树实现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
const int N=1000050;
int n,m,w[N];
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
namespace Persistable_SGT
{
struct node{int l,r,val;} t[N*25];
int rt[N],cnt=0,pos;
void build(int &o,int l,int r)
{
o=++cnt;
if (l==r) {t[o].val=w[r];return;}
int mid=(l+r)>>1;
build(t[o].l,l,mid);
build(t[o].r,mid+1,r);
}
void insert(int &o,int pre,int l,int r,int x)
{
t[o=++cnt]=t[pre];
if (l==r) {t[o].val=x;return;}
int mid=(l+r)>>1;
if (pos<=mid) insert(t[o].l,t[pre].l,l,mid,x);
if (pos>mid) insert(t[o].r,t[pre].r,mid+1,r,x);
}
int query(int o,int l,int r)
{
if (l==r) return t[o].val;
int mid=(l+r)>>1;
if (pos<=mid) return query(t[o].l,l,mid);
if (pos>mid) return query(t[o].r,mid+1,r);
}
};
using namespace Persistable_SGT;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) w[i]=read();
build(rt[0],1,n);
for(int i=1;i<=m;i++)
{
int pre=read(),opt=read();
pos=read();
if (opt==1) insert(rt[i],rt[pre],1,n,read());
if (opt==2) printf("%d\n",query(rt[i]=rt[pre],1,n));
}
return 0;
}