CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

===== 洛谷3369 可持久化平衡树 =====

<code cpp>
#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;
}
</code>

CVBB ACM Team

用户工具

站点工具

页面工具