题目地址：BZOJ：Problem 3685. — 普通van Emde Boas树

题目描述

设计数据结构支持:
1 x 若x不存在,插入x
2 x 若x存在,删除x
3 输出当前最小值,若不存在输出-1
4 输出当前最大值,若不存在输出-1
5 x 输出x的前驱,若不存在输出-1
6 x 输出x的后继,若不存在输出-1
7 x 若x存在,输出1,否则输出-1

输入输出格式

输入格式：
第一行给出n,m 表示出现数的范围和操作个数
接下来m行给出操作
n<=10^6,m<=2*10^6,0<=x<n

输出格式：

输入输出样例

输入样例#1：

10 11
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2

输出样例#1：

1
-1
2
2
2
-1

题解

虽说是vEB树的题，好像可以用权值线段树水过去，反正复杂度都是$O(n \log n)$。这里用了一个比较tricky的写法，把全局最大最小和前驱后继合并到一起，写成查区间最大最小了。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

int has[MAXN];

#define lch o << 1
#define rch o << 1 | 1
#define mid ((l + r) >> 1)

int sgt[MAXN << 2];

inline void insert(int o, int l, int r, int x) {
    if(l == r) {
        sgt[o] = 1; return;
    }
    if(x <= mid) insert(lch, l, mid, x);
    else insert(rch, mid + 1, r, x);
    sgt[o] = sgt[lch] + sgt[rch];
}

inline void erase(int o, int l, int r, int x) {
    if(l == r) {
        sgt[o] = 0; return;
    }
    if(x <= mid) erase(lch, l, mid, x);
    else erase(rch, mid + 1, r, x);
    sgt[o] = sgt[lch] + sgt[rch];
}

// [0, x)
inline int querymx(int o, int l, int r, int x) {
    if(l == r) return sgt[o] && l != x ? l : -1;
    if(x <= mid) {
        return querymx(lch, l, mid, x);
    } else if(x <= r) {
        int res = querymx(rch, mid + 1, r, x);
        return res == -1 ? querymx(lch, l, mid, x) : res;
    } else {
        if(sgt[rch]) return querymx(rch, mid + 1, r, x);
        else return querymx(lch, l, mid, x);
    }
}

// (x, inf)
inline int querymn(int o, int l, int r, int x) {
    if(l == r) return sgt[o] && l != x ? l : -1;
    if(x > mid) {
        return querymn(rch, mid + 1, r, x);
    } else if(x >= l) {
        int res = querymn(lch, l, mid, x);
        return res == -1 ? querymn(rch, mid + 1, r, x) : res;
    } else {
        if(sgt[lch]) return querymn(lch, l, mid, x);
        else return querymn(rch, mid + 1, r, x);
    }
}

int n, m;

int main() {
    memset(has, -1, sizeof(has));
    n = readint(); m = readint();
    while(m--) {
        int op, x;
        op = readint();
        if(op != 3 && op != 4) x = readint();
        if(op == 1) {
            has[x] = 1;
            insert(1, 0, n - 1, x);
        } else if(op == 2) {
            has[x] = -1;
            erase(1, 0, n - 1, x);
        } else if(op == 3) {
            printf("%d\n", querymn(1, 0, n - 1, -1));
        } else if(op == 4) {
            printf("%d\n", querymx(1, 0, n - 1, n));
        } else if(op == 5) {
            printf("%d\n", querymx(1, 0, n - 1, x));
        } else if(op == 6) {
            printf("%d\n", querymn(1, 0, n - 1, x));
        } else {
            printf("%d\n", has[x]);
        }
    }
    return 0;
}