可持续化线段树

最后一个点TLE了,不知道怎么优化。

#include<bits/stdc++.h>
using namespace std;
struct kkk{
	int val,lc,rc;
}sgt[80000800];
int a[1000010],ver[1000010],tot;
int build(int begin,int end){
	if(begin == end){
		tot++;
		sgt[tot].val = a[begin];
		return tot;
	}
	tot++;
	int mid = (begin+end)/2;
	int u = tot;
	sgt[u].lc = build(begin,mid);
	sgt[u].rc = build(mid+1,end);
	return u;
}
int ins(int index,int begin,int end,int id,int x){
	if(begin == end){
		tot++;
		sgt[tot].val = x;
		return tot;
	}
	tot++;
	int u = tot;
	int mid = (begin+end)/2;
	if(id <= mid){
		sgt[u].lc = ins(sgt[index].lc,begin,mid,id,x);
		sgt[u].rc = sgt[index].rc;
	}
	else{
		sgt[u].lc = sgt[index].lc;
		sgt[u].rc = ins(sgt[index].rc,mid+1,end,id,x);
	}
	return u;	 
}
int gets(int index,int begin,int end,int id){
	if(begin == end){
		return sgt[index].val;
	}
	int mid = (begin+end)/2;
	if(id <= mid){
		return gets(sgt[index].lc,begin,mid,id);
	}
	else{
		return gets(sgt[index].rc,mid+1,end,id);
	}
}
int cnt;
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
	}
	ver[0] = build(1,n);
	cnt++;
	while(m--){
		int v,op;
		cin>>v>>op;
		if(op == 1){
			int lo,val;
			cin>>lo>>val;
			ver[cnt] = ins(ver[v],1,n,lo,val);
			cnt++;
		} 
		else{
			int id;
			cin>>id;
			ver[cnt] = ver[v];
			cnt++; 
			cout<<gets(ver[v],1,n,id)<<endl;
		}
	}
	return 0;
}