为什么这个 Treap 在适用 vector 实现时会出错？

类似的问题也出现在了线段树、主席树等代码中，但跳表没问题

以下两份代码适用于 P3369。

数组实现：

#include<bits/stdc++.h>
using namespace std;
struct Treap
{
	const int INF = 1e8;
	struct node
	{
		int l,r;
		int key,val;
		int cnt,siz;
	}t[100005];
	int root,cnt;
	int get_node(int key)
	{
		t[++cnt] = (node){0,0,key,rand(),1,1};
		return cnt;
	}
	void pushup(int p)
	{
		t[p].siz = t[t[p].l].siz + t[t[p].r].siz + t[p].cnt;
	}
	void zig(int &p)
	{
		int q = t[p].l;
		t[p].l = t[q].r;t[q].r = p;p = q;
		pushup(t[p].r);pushup(p);
	}
	void zag(int &p)
	{
		int q = t[p].r;
		t[p].r = t[q].l;t[q].l = p;p = q;
		pushup(t[p].l);pushup(p);
	}
	void build()
	{
		root = get_node(-INF);
		t[root].r = get_node(INF);
		if(t[1].val < t[2].val)zag(root);
		else pushup(root);
	}
	void add(int &p,int key)
	{
		if(!p)p = get_node(key);
		else if(t[p].key == key)t[p].cnt++;
		else if(t[p].key > key)
		{
			add(t[p].l,key);
			if(t[t[p].l].val > t[p].val)zig(p);
		}
		else
		{
			add(t[p].r,key);
			if(t[t[p].r].val > t[p].val)zag(p);
		}
		pushup(p);
	}
	void del(int &p,int key)
	{
		if(!p)return;
		if(t[p].key == key)
		{
			if(t[p].cnt > 1)t[p].cnt--;
			else if(t[p].l||t[p].r)
			{
				if(!t[p].r||t[t[p].l].val > t[t[p].r].val)
					zig(p),del(t[p].r,key);
				else zag(p),del(t[p].l,key);
			}
			else p = 0;
		}
		else if(t[p].key > key)del(t[p].l,key);
		else del(t[p].r,key);
		pushup(p);
	}
	int Get_rank(int p,int key)
	{
		if(!p)return 1;
		if(t[p].key == key)return t[t[p].l].siz + 1;
		if(t[p].key > key)return Get_rank(t[p].l,key);
		return t[t[p].l].siz + t[p].cnt + Get_rank(t[p].r,key);
	}
	int Get_val(int p,int rank)
	{
		if(!p)return INF;
		if(t[t[p].l].siz >= rank)return Get_val(t[p].l,rank);
		if(t[t[p].l].siz + t[p].cnt >= rank)return t[p].key;
		return Get_val(t[p].r,rank - t[t[p].l].siz - t[p].cnt);
	}
	int Get_pre(int p,int key)
	{
		if(!p)return -INF;
		if(t[p].key >= key)return Get_pre(t[p].l,key);
		return max(t[p].key,Get_pre(t[p].r,key));
	}
	int Get_nxt(int p,int key)
	{
		if(!p)return INF;
		if(t[p].key <= key)return Get_nxt(t[p].r,key);
		return min(t[p].key,Get_nxt(t[p].l,key));
	}
}treap;
int n,opt,x;
int main()
{
	treap.build();
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d %d",&opt,&x);
		if(opt == 1)treap.add(treap.root,x);
		else if(opt == 2)treap.del(treap.root,x);
		else if(opt == 3)
			printf("%d\n",treap.Get_rank(treap.root,x) - 1);
		else if(opt == 4)
			printf("%d\n",treap.Get_val(treap.root,x + 1));
		else if(opt == 5)
			printf("%d\n",treap.Get_pre(treap.root,x));
		else 
			printf("%d\n",treap.Get_nxt(treap.root,x));
	}
}

vector 实现：

#include<bits/stdc++.h>
using namespace std;
struct Treap
{
	const int INF = 1e8;
	struct node
	{
		int l,r;
		int key,val;
		int cnt,siz;
	}emp;
	vector <node> t;
	int root,cnt;
	int init()
	{
		t.push_back(emp);
	} 
	int get_node(int key)
	{
		t.push_back(emp);
		t[++cnt] = (node){0,0,key,rand(),1,1};
		return cnt;
	}
	void pushup(int p)
	{
		t[p].siz = t[t[p].l].siz + t[t[p].r].siz + t[p].cnt;
	}
	void zig(int &p)
	{
		int q = t[p].l;
		t[p].l = t[q].r;t[q].r = p;p = q;
		pushup(t[p].r);pushup(p);
	}
	void zag(int &p)
	{
		int q = t[p].r;
		t[p].r = t[q].l;t[q].l = p;p = q;
		pushup(t[p].l);pushup(p);
	}
	void build()
	{
		root = get_node(-INF);
		t[root].r = get_node(INF);
		if(t[1].val < t[2].val)zag(root);
		else pushup(root);
	}
	void add(int &p,int key)
	{
		if(!p)p = get_node(key);
		else if(t[p].key == key)t[p].cnt++;
		else if(t[p].key > key)
		{
			add(t[p].l,key);
			if(t[t[p].l].val > t[p].val)zig(p);
		}
		else
		{
			add(t[p].r,key);
			if(t[t[p].r].val > t[p].val)zag(p);
		}
		pushup(p);
	}
	void del(int &p,int key)
	{
		if(!p)return;
		if(t[p].key == key)
		{
			if(t[p].cnt > 1)t[p].cnt--;
			else if(t[p].l||t[p].r)
			{
				if(!t[p].r||t[t[p].l].val > t[t[p].r].val)
					zig(p),del(t[p].r,key);
				else zag(p),del(t[p].l,key);
			}
			else p = 0;
		}
		else if(t[p].key > key)del(t[p].l,key);
		else del(t[p].r,key);
		pushup(p);
	}
	int Get_rank(int p,int key)
	{
		if(!p)return 1;
		if(t[p].key == key)return t[t[p].l].siz + 1;
		if(t[p].key > key)return Get_rank(t[p].l,key);
		return t[t[p].l].siz + t[p].cnt + Get_rank(t[p].r,key);
	}
	int Get_val(int p,int rank)
	{
		if(!p)return INF;
		if(t[t[p].l].siz >= rank)return Get_val(t[p].l,rank);
		if(t[t[p].l].siz + t[p].cnt >= rank)return t[p].key;
		return Get_val(t[p].r,rank - t[t[p].l].siz - t[p].cnt);
	}
	int Get_pre(int p,int key)
	{
		if(!p)return -INF;
		if(t[p].key >= key)return Get_pre(t[p].l,key);
		return max(t[p].key,Get_pre(t[p].r,key));
	}
	int Get_nxt(int p,int key)
	{
		if(!p)return INF;
		if(t[p].key <= key)return Get_nxt(t[p].r,key);
		return min(t[p].key,Get_nxt(t[p].l,key));
	}
}treap;
int n,opt,x;
int main()
{
	treap.init();
	treap.build();
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d %d",&opt,&x);
		if(opt == 1)treap.add(treap.root,x);
		else if(opt == 2)treap.del(treap.root,x);
		else if(opt == 3)
			printf("%d\n",treap.Get_rank(treap.root,x) - 1);
		else if(opt == 4)
			printf("%d\n",treap.Get_val(treap.root,x + 1));
		else if(opt == 5)
			printf("%d\n",treap.Get_pre(treap.root,x));
		else 
			printf("%d\n",treap.Get_nxt(treap.root,x));
	}
}