洛谷3369 可持久化平衡树
#include "ext/rope"
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
using namespace __gnu_cxx;
#define MAXN 500006
rope<int> nums[MAXN];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int v, opt, x;
scanf("%d%d%d", &v, &opt, &x);
nums[i] = nums[v];
if (opt == 1)
nums[i].insert(lower_bound(nums[i].begin(), nums[i].end(), x) - nums[i].begin(), x);
if (opt == 2) {
auto it = lower_bound(nums[i].begin(), nums[i].end(), x);
if (it != nums[i].end() && *it == x) nums[i].erase(it - nums[i].begin(), 1);
}
if (opt == 3)
printf("%d\n", (int) (lower_bound(nums[i].begin(), nums[i].end(), x) - nums[i].begin()) + 1);
if (opt == 4)
printf("%d\n", *(nums[i].begin() + x - 1));
if (opt == 5) {
auto it = lower_bound(nums[i].begin(), nums[i].end(), x);
if (it == nums[i].begin() - 1) puts("-2147483647");
else --it, printf("%d\n", *it);
}
if (opt == 6) {
auto it = upper_bound(nums[i].begin(), nums[i].end(), x);
if (it == nums[i].end()) puts("2147483647");
else printf("%d\n", *it);
}
}
return 0;
}