普通平衡树

Posted by EtaoinWu on 周四 29 九月 2016
/**
 * @author Etaoin
 * @license WTFPL
 **********************************************************************
 * This program is free software. It comes without any warranty, to   *
 * the extent permitted by applicable law. You can redisttribute it    *
 * and/or modify it under the terms of the Do What The Fuck You Want  *
 * To Public License, Version 2, as published by Sam Hocevar. See     *
 * http://www.wtfpl.net/ for more details.                            *
 **********************************************************************
 * @school Hangzhou No.2 High School
 */
#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define rep(a,b,c) for(int a = b;a <= c;a++)
#define REP(a,b,c) for(int a = b;a <  c;a++)
#define per(a,b,c) for(int a = b;a >= c;a--)
#define PER(a,b,c) for(int a = b;a >  c;a--)

#ifdef debug
    #include <conio.h>
    #define debugdo(x) x
    #define debugndo(x)
#else
    #define debugdo(x)
    #define debugndo(x) x
#endif

#define inf 1000000000
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}
int n;
vector<int> a;
void insert(int x)
{
    a.insert(upper_bound(a.begin(), a.end(), x), x);
    return;
}
void del(int x)
{
    a.erase(lower_bound(a.begin(), a.end(), x));
    return;
}
int find(int x)
{
    return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
}
int main()
{
    n = read();
    a.reserve(200000);
    int f, x;

    for (int i = 1; i <= n; i++) {
        f = read();
        x = read();

        switch (f) {
        case 1:
            insert(x);
            break;

        case 2:
            del(x);
            break;

        case 3:
            printf("%d\n", find(x));
            break;

        case 4:
            printf("%d\n", a[x - 1]);
            break;

        case 5:
            printf("%d\n", *--lower_bound(a.begin(), a.end(), x));
            break;

        case 6:
            printf("%d\n", *upper_bound(a.begin(), a.end(), x));
            break;
        }
    }

    return 0;
}

tags: LJOJ, STL