Description

您需要写一种数据结构 (可参考题目标题), 来维护一些数, 其中需要提供以下操作:

  1. 插入 x 数
  2. 删除 x 数 (若有多个相同的数, 因只删除一个)
  3. 查询 x 数的排名 (若有多个相同的数, 因输出最小的排名)
  4. 查询排名为 x 的数
  5. 求 x 的前驱 (前驱定义为小于 x, 且最大的数)
  6. 求 x 的后继 (后继定义为大于 x, 且最小的数)

Input

第一行为 \(n\), 表示操作的个数, 下面 n 行每行有两个数 \(opt\) 和 \(x\),\(opt\) 表示操作的序号 \((1 \leq opt \leq 6)\)

Output

对于操作 \(3, 4, 5, 6\) 每行输出一个数, 表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

Data Range

\(n\) 的数据范围:\(n \leq 100000\)

每个数的数据范围:\([-10^7,10^7]\)

数据参见:http://pan.baidu.com/s/1jHMJwO2

Explanation

这道题调了两个晚上好不好~

就是一个平衡树, 用 Splay 可以很不水地过掉 (因为本人写 Splay 总是写炸对不对, 不然 怎么会叫 Splay With Trees...... ) . 但是这样的平衡树我们还需要给他一点小 Trick, 比如 在每一个节点上打一个标记记一下这个节点实际出现了几次, 然后就把判重的情况给搞定了.

其他的还有奇葩的前继后继查询, 像这个搞了半天然后最后实在是没有什么办法了, 在 find_value() 上瞎搞了一发, 加了一堆 return, 然后又添加了一个函数 find_value_indet(), 代表不确定的查询 lower bound, 终于可以过掉样例了......

结果突然发现过了样例那 1. 6M 的数据就可以直接水过了 (你知道用 pyjudge 测评的时候我都是捂着眼睛测的 233)

然后交到 BZOJ 上 1A, 算我运气好...... @Burst_Zero 直接因为用了 cincout 被奇怪地卡成 RE 不知道为什么 (hustoj 好奇怪)

居然把 Splay 在 OJ 上过掉了好开心~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 200100;
const int infinit = 10e8;

class SplayTree
{
public:
    int n, root, ncnt;
    int ch[maxn][2], par[maxn];
    int val[maxn], vsz[maxn], size[maxn];
    #define lc(__x) ch[__x][0]
    #define rc(__x) ch[__x][1]
    int make_node(int v)
    {
        int p = ++ncnt;
        val[p] = v;
        lc(p) = rc(p) = par[p] = 0;
        vsz[p] = 1;
        size[p] = 1;
        return p;
    }
    void rotate(int p)
    {
        int q = par[p], g = par[q];
        int x = p == rc(q), y = q == rc(g);
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par[ch[q][x]] = q;
        ch[p][!x] = q; par[q] = p;
        if (g) ch[g][y] = p; par[p] = g;
        // Updating data
        size[q] = size[lc(q)] + size[rc(q)] + vsz[q];
        size[p] = size[lc(p)] + size[rc(p)] + vsz[p];
        return ;
    }
    void splay(int p, int t)
    {
        for (int q = 0; (q = par[p]) && q != t; rotate(p))
            if (par[q] && par[q] != t)
                rotate((p == lc(q)) == (q == lc(par[q])) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int suc(int p)
    {
        if (!rc(p)) { while (p && p == rc(par[p])) p = par[p]; p = par[p]; }
        else { p = rc(p); while (p && lc(p)) p = lc(p); }
        return p;
    }
    int pre(int p)
    {
        if (!lc(p)) { while (p && p == lc(par[p])) p = par[p]; p = par[p]; }
        else { p = lc(p); while (p && rc(p)) p = rc(p); }
        return p;
    }
    int find_size(int sz)
    {
        sz += 1; // Hot-fix.
        int p = root;
        while (p != 0) {
            if (sz <= size[lc(p)]) {
                p = lc(p);
                continue;
            } sz -= size[lc(p)];
            if (sz <= vsz[p]) return p;
            sz -= vsz[p]; p = rc(p);
        }
        return p;
    }
    int query_rank(int v)
    {
        int p = root, res = 0;
        while (p != 0) {
            if (v < val[p]) { p = lc(p); continue; }
            res += size[lc(p)];
            if (v == val[p]) return (res + 1) - 1;
            res += vsz[p];
            p = rc(p);
        }
        return res - 1;
    }
    int find_value(int v)
    {
        int p = root;
        while (p != 0) {
            if (v < val[p]) {
                if (lc(p)) p = lc(p);
                else return p;
                continue;
            } else if (v == val[p])
                return p;
            if (rc(p)) p = rc(p);
            else return p;
        }
        return p;
    }
    int find_value_indet(int v)
    {
        int p = find_value(v);
        while (p && val[p] > v)
            p = pre(p);
        return p;
    }
    void insert(int v)
    {
        int p = root;
        while (lc(p) || rc(p)) {
            size[p]++;
            if (v < val[p]) {
                if (lc(p)) p = lc(p);
                else break;
            } else if (v == val[p]) {
                break;
            } else {
                if (rc(p)) p = rc(p);
                else break;
            }
        }
        if (v == val[p]) {
            splay(p, 0);
            vsz[p]++, size[p]++;
            return ;
        }
        // No existent point to serve as lazy insertion
        int q = make_node(v);
        par[q] = p;
        if (v <= val[p]) lc(p) = q;
        else rc(p) = q;
        splay(q, 0);
        return ;
    }
    void remove(int p)
    {
        splay(p, 0);
        // Large enough so that removal is unnecessary
        if (vsz[p] > 1) {
            vsz[p]--;
            size[p]--;
            return ;
        }
        // Removing node from tree
        int lp = pre(p), rp = suc(p);
        splay(lp, 0);
        splay(rp, root);
        lc(rp) = 0;
        size[rp]--; size[lp]--;
        return ;
    }
    void init(void)
    {
        root = make_node(-infinit);
        rc(root) = make_node(infinit);
        par[rc(root)] = root;
        size[root] = 2;
        return ;
    }
} st;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    st.init();
    for (int i = 1; i <= n; i++) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
            st.insert(x);
        else if (opt == 2)
            st.remove(st.find_value(x));
        else if (opt == 3)
            printf("%d\n", st.query_rank(x));
        else if (opt == 4)
            printf("%d\n", st.val[st.find_size(x)]);
        else if (opt == 5) {
            int p = st.find_value_indet(x);
            if (st.val[p] == x) p = st.pre(p);
            printf("%d\n", st.val[p]); }
        else if (opt == 6) {
            int p = st.suc(st.find_value_indet(x));
            printf("%d\n", st.val[p]); }
    }
    return 0;
}