使用rope

已经进行空间优化(自以为）

MLE on #19 #20

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/rope>
#define N 400006

using namespace __gnu_cxx;
using namespace std;

rope<int> num[N];
int n, u;

int cnt;
int bac[500001];
int ys[500001];

inline int read(){
	register int x = 0, f = 1; register char ch = getchar();
	for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1;
	for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
}

int find(int now){
	return ((bac[now] == now) ? now : bac[now] = find(bac[now]));
}

int main(){
	n = read();
	num[0] = rope<int>();
	for(int i = 1; i <= n; ++ i){
		register int v = read(), opt = read(), x = read();
		if(opt == 1 || opt == 2){
			bac[i] = i;
			ys[i] = ++ cnt;
			num[cnt] = rope<int>(num[ys[find(v)]]);
			u = cnt;
		}
		else{
			bac[i] = find(v);
			u = ys[bac[i]];
		}
		if(opt == 1){
			num[u].insert(lower_bound(num[u].begin(), num[u].end(), x) - num[u].begin(), x);
		}
		if(opt == 2){
			auto it = lower_bound(num[u].begin(), num[u].end(), x);
			if(it != num[u].end() && *it == x) num[u].erase(it - num[i].begin(), 1); 
		}
		if(opt == 3){
			printf("%d\n", (int)(lower_bound(num[u].begin(), num[u].end(), x) - num[u].begin()) + 1);
		}
		if(opt == 4){
			printf("%d\n", *(num[u].begin() + x - 1));
		}
		if(opt == 5){
			auto it = lower_bound(num[u].begin(), num[u].end(), x);
			if(it == num[u].begin() - 1) puts("-2147483647");
			else --it, printf("%d\n", *it);
		}
		if(opt == 6){
			auto it = upper_bound(num[u].begin(), num[u].end(), x);
			if(it == num[u].end()) puts("214783647");
			else printf("%d\n", *it);
		}
	}
	return 0;
}