题目描述：
假如现在有一个序列a[]，有两种操作   
1、给出k，在原序列第k和k+1个数之间插入一个数
2、给出k，询问当前第k个数是多少

假如我们使用数组维护，那么插入操作的时间复杂度是O(n)，查询操作的时间复杂度是O(1)

时我们也知道了用指针可以完成这个问题，那么我们是否可以用数组来模拟指针的情况呢？

输入格式：
第一行两个数 n, q ，表示原序列长度为 n ，操作次数为 q
第二行包括 n 个数，表示原序列

接下来 q 行每行第一个数 op 表示操作类型
1 操作包括两个数 k, val 表示在第 k 和第 k + 1 个数之间插入一个数 val  
2 操作包括一个数 k  表示询问第 k 个数的值 

输出格式：
输出包括若干行，每行对应一个 2 操作询问的结果

input：
3 2
3 2 1
1 2 4
2 3

output：
4

代码$↓↓↓↓↓↓↓↓↓↓$

#include<bits/stdc++.h>
using namespace std;
// 定义cur指向数组的最后一个元素，list[0][i]表示value，list[1][i]表示point 
int cur, n, q, _list[2][400001], head; 

// 将一个元素加入到链表的头部 
void add_to_head(int x){
	_list[0][++cur] = x;
	// 如果不是第一个元素，将前一个元素指向当前的元素 
	if(cur > 1) _list[1][cur - 1] = cur;
}

// 插入元素于链表的k位置的后面，value为x
void _insert(int k, int x){
	// 新建b 
	_list[0][++cur] = x;
	// a  b->c->d
	_list[1][cur] = k + 1;
	// a->b->c->d
	if(k >= 1) _list[1][k] = cur;
	// 特判k=0的情况 
	else{
		_list[1][cur] = head;
		head = cur;
	}
}
 
int main(){
	// 开始没有元素 
	cur = 0;
	head = 1;
	cin >> n >> q;
	// 每输入一个数，将这个数加入到链表后面
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x;	
		add_to_head(x);
	}
	for(int i = 1; i <= q; i++){
		int op;
		cin >> op;
		if(op == 1){
			int k, x;
			cin >> k >> x;
			_insert(k, x);
		}
		else if(op == 2){
			int x, pre = head;
			cin >> x; 
			for(int i = 1; i <= x - 1; i++) pre = _list[1][pre];
			cout << _list[0][pre] <<endl; 
		} 
	}
	
	return 0;
} 

70分：wa3个点