https://www.luogu.com.cn/record/44635909

萌新调不动了啊。。。

40pts

//_SEGMENT_tree
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<fstream>
#include<cmath>
using namespace std;
#define N 1000005 
inline int read()
{
    int x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
struct segment
{
  int lson,rson,val;
}tree[N<<5]; 
#define ls(i) tree[i].lson
#define rs(i) tree[i].rson
#define val(i) tree[i].val
int tot,root[N],a[N],n,m,total;
inline int build(int l,int r)
{
	int now=++tot;
	if(l==r) 
	{
	val(now)=read();
	return now;	
	}
	int mid=(l+r)>>1;
	ls(now)=build(l,mid);
	rs(now)=build(mid+1,r);
	return now;
}
inline int modify(int pre,int l,int r,int x,int t)
{
	int now=++tot;
	if(l==r) 
	{
	val(now)=t;
	return now;	
	}
	ls(now)=ls(pre);
	rs(now)=rs(pre); 
	int mid=(l+r)>>1;
	if(x<=mid)
	ls(now)=modify(ls(pre),l,mid,x,t);
	else
	rs(now)=modify(rs(pre),mid+1,r,x,t);
	return now;
}
inline void query(int pre,int l,int r,int x)
{
	if(l==r) 
	{
	printf("%d\n",val(pre));
	return ;	
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	query(ls(pre),l,mid,x);
	else
	query(rs(pre),mid+1,r,x);
	return ;
}
int main()
{
 n=read(); m=read();
 root[++total]=build(1,n);
 for(int i=1;i<=m;i++)
 {
 	int to_where=read()+1,op=read();
 	if(op==1)
 	{
 	 int u=read(),v=read();
	 root[++total]=modify(root[to_where],1,n,u,v); 	
	}
	if(op==2)
	{
	 int u=read();
	 root[++total]=root[to_where];
	 query(root[to_where],1,n,u);
	}
 }
 return 0;
}