题目大意：需要维护一个长度为 N 的数组，支持在历史版本上单点修改和单点查询。

题解：显然，如果直接暴力维护的话会 MLE。因此，采用线段树进行维护，使得空间复杂度由 \(O(mn)\) 降至 \(O(mlogn)\)，不过相应的时间复杂度由 \(O(1)\) 上升至 \(O(logn)\)。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

inline int read(){

    int f=1,x=0;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');

    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');

    return f*x;

}

int n,m,a[maxn];

struct node{

	#define ls(x) t[x].lc

	#define rs(x) t[x].rc

	int lc,rc,val;

}t[maxn*20];

int tot,root[maxn],cnt;

int build(int l,int r){

	int x=++tot;

	if(l==r){t[x].val=a[l];return x;}

	int mid=l+r>>1;

	ls(x)=build(l,mid),rs(x)=build(mid+1,r);

	return x;

}

int modify(int pre,int l,int r,int pos,int val){

	int x=++tot;

	t[x]=t[pre];

	if(l==r){t[x].val=val;return x;}

	int mid=l+r>>1;

	if(pos<=mid)ls(x)=modify(ls(pre),l,mid,pos,val);

	else rs(x)=modify(rs(pre),mid+1,r,pos,val);

	return x;

}

int query(int x,int l,int r,int pos){

	if(l==r)return t[x].val;

	int mid=l+r>>1;

	if(pos<=mid)return query(ls(x),l,mid,pos);

	else return query(rs(x),mid+1,r,pos);

}

void read_and_parse(){

	n=read(),m=read();

	for(int i=1;i<=n;i++)a[i]=read();

	root[0]=build(1,n);

}

void solve(){

	while(m--){

		int i=read(),opt=read();

		if(opt==1){

			int pos=read(),val=read();

			root[++cnt]=modify(root[i],1,n,pos,val);

		}else{

			int pos=read();

			root[++cnt]=root[i];

			printf("%d\n",query(root[cnt],1,n,pos));

		}

	}

}

int main(){

	read_and_parse();

	solve();

	return 0;

}