BZOJ3685 普通van Emde Boas树 zkw线段树

yts1999 posted @ 2015年8月01日 17:45 in zkw线段树 with tags bzoj zkw线段树 , 500 阅读

zkw线段树好厉害。。。

/**************************************************************
    Problem: 3685
    User: yts1999
    Language: C++
    Result: Accepted
    Time:6696 ms
    Memory:9476 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
 
int t[2100010];
int q;
 
void add(int x) {
    x += q;
    if (t[x])
        return;
    for (; x; x >>= 1)
        t[x]++;
}
 
void del(int x) {
    x += q;
    if (! t[x])
        return;
    for (; x; x >>= 1)
        t[x]--;
}
 
int get_min() {
    if (! t[1])
        return 0;
    int x;
    for (x = 1; x <= q; x = t[x << 1]?x << 1:x << 1 | 1);
    return x - q;
}
 
int get_max() {
    if (! t[1])
        return 0;
    int x;
    for (x = 1; x <= q; x = t[x << 1 | 1]?x << 1 | 1:x << 1);
    return x - q;
}
 
int get_pred(int x) {
    for (x += q; x ^ 1; x >>= 1)
        if (x & 1 && t[x >> 1] > t[x])
            break;
    if (x == 1)
        return 0;
    for (x ^= 1; x <= q; x = t[x << 1 | 1]?x << 1 | 1:x << 1);
    return x - q;
}
 
int get_succ(int x) {
    for (x += q; x ^ 1; x >>= 1)
        if (~ x & 1 && t[x >> 1] > t[x])
            break;
    if (x == 1)
        return 0;
    for (x ^= 1; x <= q; x = t[x << 1]?x << 1:x << 1 | 1);
    return x - q;
}
 
int exsist(int x) {
    return t[x + q]?1:-1;
}
 
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (q = 1; q <= n; q <<= 1);
    for (int i = 0; i < m; i++) {
        int op;
        scanf("%d",&op);
        if (op == 1) {
            int x;
            scanf("%d",&x);
            add(x + 1);
        }
        if (op == 2) {
            int x;
            scanf("%d",&x);
            del(x + 1);
        }
        if (op == 3)
            printf("%d\n",get_min() - 1);
        if (op == 4)
            printf("%d\n",get_max() - 1);
        if (op == 5) {
            int x;
            scanf("%d",&x);
            printf("%d\n",get_pred(x + 1) - 1);
        }
        if (op == 6) {
            int x;
            scanf("%d",&x);
            printf("%d\n",get_succ(x + 1) - 1);
        }
        if (op == 7) {
            int x;
            scanf("%d",&x);
            printf("%d\n",exsist(x + 1));
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter