数组实现，按照 blog 说的 split 和 merge 都新开节点。

感觉非常突兀且奇异，测评记录 click here。具体代码见下：

#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;

const int MAXM = 5e5 + 5;

int m, version[MAXM];

namespace FHQ {
	
	const int MAXMEM = MAXM * 56;
	
#define NOELEMENTP 0x7fffffff
#define NOELEMENTN 0x80000001
	
	int finish = 1;
	int l[MAXMEM], r[MAXMEM], v[MAXMEM];
	int rk[MAXMEM], cnt[MAXMEM], siz[MAXMEM];
	
	int copyNode(int x) {
		if (x == 0)
			return 0;
		rk[finish] = rk[x];
		l[finish] = l[x];
		r[finish] = r[x];
		v[finish] = v[x];
		cnt[finish] = cnt[x];
		siz[finish] = siz[x];
		return finish ++;
	}
	
	int newNode(int vv) {
		rk[finish] = rand();
		v[finish] = vv;
		cnt[finish] = siz[finish] = 1;
		return finish ++;
	}
	
	void pushup(int x) {
		siz[x] = siz[l[x]] + siz[r[x]] + cnt[x];
	}
	
	pair<int, int> splitV(int value, int rt) {
		// {[1, value], (value, max]}
		if (!rt)
			return make_pair(0, 0);
		rt = copyNode(rt);
		pair<int, int> temp;
		if (value >= v[rt]) {
			temp = splitV(value, r[rt]);
			r[rt] = temp.first;
			pushup(rt);
			return make_pair(rt, temp.second);
		}
		temp = splitV(value, l[rt]);
		l[rt] = temp.second;
		pushup(rt);
		return make_pair(temp.first, rt);
	}
	
	int merge(int A, int B) {
		if (!A || !B)
			return A ^ B;
		int res;
		if (rk[A] < rk[B]) {
			res = copyNode(A);
			r[res] = merge(r[A], B);
		} else {
			res = copyNode(B);
			l[res] = merge(A, l[B]);
		}
		pushup(res);
		return res;
	}
	
	int add(int key, int vv, int rt) {
		int res = copyNode(rt);
		if (v[res] == vv)
			cnt[res] += vv;
		else if (v[res] > vv)
			l[res] = add(key, vv, l[res]);
		else
			r[res] = add(key, vv, r[res]);
		pushup(res);
		return res;
	}
	
	int findge(int vv, int rt) {
		// 找第一个 >= vv 的节点
		int bigger = 0;
		while (rt) {
			if (v[rt] == vv)
				return rt;
			if (v[rt] > vv)
				bigger = rt, rt = l[rt];
			else
				rt = r[rt];
		}
		return bigger;
	}
	
	int findle(int vv, int rt) {
		// 找到第一个 <= vv 的节点
		int les = 0;
		while (rt) {
			if (v[rt] == vv)
				return rt;
			if (v[rt] < vv)
				les = rt, rt = r[rt];
			else
				rt = l[rt];
		}
		return les;
	}
	
	int pre(int vv, int rt) {
		int res = findle(vv, rt);
		if (res == 0)
			return NOELEMENTN;
		if (v[res] != vv)
			return v[res];
		res = findle(v[res] - 1, rt);
		return res ? v[res] : NOELEMENTN;
	}
	
	int nxt(int vv, int rt) {
		int res = findge(vv, rt);
		if (res == 0)
			return NOELEMENTP;
		if (v[res] != vv)
			return v[res];
		res = findge(v[res] + 1, rt);
		return res ? v[res] : NOELEMENTP;
	}
	
	int getrank(int vv, int rt) {
		int res = 0;
		while (rt) {
			if (v[rt] == vv)
				return res + 1;
			if (v[rt] > vv)
				rt = l[rt];
			else
				res += siz[l[rt]] + cnt[rt], rt = r[rt];
		}
		return res + 1;
	}
	
	int getvalue(int rk, int rt) {
		while (true) {
			int ll = siz[l[rt]] + 1, rr = siz[l[rt]] + cnt[rt];
			if (rk < ll)
				rt = l[rt];
			else if (rk > rr)
				rk -= rr, rt = r[rt];
			else
				return v[rt];
		}
	}
	
	int ins(int vv, int rt) {
		int got = findge(vv, rt);
		if (got && v[got] == vv)
			return add(vv, 1, rt);
		pair<int, int> temp = splitV(vv, rt);
		return merge(merge(temp.first, newNode(vv)), temp.second);
	}
	
	int del(int vv, int rt) {
		int got = findge(vv, rt);
		if (got == 0 || v[got] != vv)
			return copyNode(rt);
		if (cnt[got] > 1)
			return add(vv, -1, rt);
		pair<int, int> temp1 = splitV(vv, rt);
		pair<int, int> temp2 = splitV(vv - 1, temp1.first);
		return merge(temp2.first, temp1.second);
	}
	
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> m;
	srand(time(NULL));
	for (int i = 1; i <= m; i ++) {
		int v, opt, x;
		cin >> v >> opt >> x;
		if (opt == 1)
			version[i] = FHQ :: ins(x, version[v]);
		else if (opt == 2)
			version[i] = FHQ :: del(x, version[v]);
		else {
			version[i] = FHQ :: copyNode(version[v]);
			if (opt == 3)
				cout << FHQ :: getrank(x, version[i]) << '\n';
			else if (opt == 4)
				cout << FHQ :: getvalue(x, version[i]) << '\n';
			else if (opt == 5)
				cout << FHQ :: pre(x, version[i]) << '\n';
			else
				cout << FHQ :: nxt(x, version[i]) << '\n';
		}
	}
	return 0;
}

没有 WA，要么 AC 要么 MLE。

经过计算，MAXM = 5e5，MAXMEM = MAXM * 56，开了 $6$ 个 int 数组，在 $1.68\times10^8$ 个 int 的量级，大概是 $640\text{ M}$ 的内存。

我想问两个问题：

1. 为什么大部分点都不到 $640\text{ M}$ ？

2. 其余的点没有一个点超过 $400\text{ M}$，为什么会如此突兀地突然暴掉成 $1.50\text{ G}$ 拉满了，数组都没这么多？

讨论区、bdfs 都没有凑到类似情况，求助见多识广的谷友们（跪