萌新刚学OI0.1毫秒，求调WBLT，样例都没过

nuo0930 @ 2021-02-04 23:20:08

#include <cstdio>
#include <cstdlib>
using std::fread;
using std::free;
using std::malloc;
using std::printf;
#ifdef ONLINE_JUDGE
#    define getchar()                                                     \
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin),    \
                      p1 == p2) ?                                         \
             EOF :                                                        \
             *p1++)
#else
using std::getchar;
#endif
#define isdigit(c) (c > 47 && c < 58)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= !(c ^ 45);
    for (; isdigit(c); c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}
struct WBLT {
    int val;
    int size;
    WBLT *lc, *rc;
    WBLT() {
        val = 0;
        size = 0;
        lc = rc = NULL;
    }
    WBLT(int a, int b, WBLT* c, WBLT* d) {
        val = a;
        size = b;
        lc = c;
        rc = c;
    }
};
inline WBLT* newnode(int a, int b, WBLT* c, WBLT* d) {
    return &(*(WBLT*)malloc(sizeof(WBLT*)) = WBLT(a, b, c, d));
}
inline WBLT* merge(WBLT* a, WBLT* b) {
    return newnode(b->val, a->size + b->size, a, b);
}
inline void left_rotate(WBLT* a) {
    a->lc = merge(a->lc, a->rc->lc);
    delete a->rc;
    a->rc = a->rc->rc;
}
inline void right_rotate(WBLT* a) {
    a->rc = merge(a->rc, a->lc->rc);
    delete a->lc;
    a->lc = a->lc->lc;
}
const int radio = 5;
inline void maintain(WBLT* a) {
    if (a->lc->size > a->rc->size * radio)
        right_rotate(a);
    else if (a->rc->size > a->lc->size * radio)
        left_rotate(a);
}
inline void pushup(WBLT* a) {
    a->size = a->lc->size + a->rc->size;
    a->val = a->rc->val;
}
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
void ins(WBLT* a, int val) {
    if (a->size == 1) {
        a->lc = newnode(min(a->val, val), 1, NULL, NULL);
        a->rc = newnode(max(a->val, val), 1, NULL, NULL);
        pushup(a);
        return;
    }
    ins(a->val > val ? a->lc : a->rc, val);
    pushup(a);
    maintain(a);
}
void del(WBLT* a, WBLT* fa, WBLT* bro, int val) {
    if (a->size == 1) {
        *fa = WBLT(bro->val, bro->size, NULL, bro);
        free(a);
        return;
    }
    if (a->val > val)
        del(a->lc, a, a->rc, val);
    else
        del(a->rc, a, a->lc, val);
    pushup(a);
    maintain(a);
}
int rank(WBLT* a, int val) {
    if (a->val == val)
        return a->size;
    if (a->val > val)
        return rank(a->lc, val);
    return rank(a->rc, val) + a->lc->size;
}
int value(WBLT* a, int rk) {
    if (a->size == rk)
        return a->val;
    if (a->lc->size > rk)
        return rank(a->lc, rk);
    return rank(a->rc, rk - a->lc->size);
}
int main() {
    int n = read();
    int m = read();
    WBLT* root = newnode(2147483647, 1, NULL, NULL);
    while (n--) {
        int x = read();
        ins(root, x);
    }
    int lastans = 0, ans = 0;
    while (m--) {
        int op, x;
        op = read();
        x = read() ^ lastans;
        switch (op) {
            case 1: {
                ins(root, x);
                break;
            }
            case 2: {
                del(root, NULL, NULL, x);
                break;
            }
            case 3: {
                lastans = rank(root, x);
                break;
            }
            case 4: {
                lastans = value(root, x);
                break;
            }
            case 5: {
                lastans = value(root, rank(root, x) - 1);
                break;
            }
            default:
                lastans = value(root, rank(root, x) + 1);
        }
        if (op != 1 && op != 2)
            ans ^= lastans;
    }
    printf("%d", ans);
    return 0;
}

by nuo0930 @ 2021-02-04 23:20:37

额，我怎么用的是小号发的

by YamadaRyou @ 2021-02-04 23:22:11

我是MLE王子的大号

by K2Cr2O7 @ 2021-02-04 23:30:44

@MLE王子 诶 printf 不用 std 的啊。

by YamadaRyou @ 2021-02-04 23:31:45

@地生王子

#include <cstdio>
#include <cstdlib>

by YamadaRyou @ 2021-02-04 23:36:43

额，问题在ins上

by SH01RuLai @ 2021-02-04 23:47:34

王 子

by nuo0930 @ 2021-02-04 23:55:14

#include <cstdio>
#include <cstdlib>
using std::fread;
using std::free;
using std::malloc;
using std::printf;
#ifdef ONLINE_JUDGE
#    define getchar()                                                     \
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin),    \
                      p1 == p2) ?                                         \
             EOF :                                                        \
             *p1++)
#else
using std::getchar;
#endif
#define isdigit(c) (c > 47 && c < 58)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0;
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= !(c ^ 45);
    for (; isdigit(c); c = getchar())
        x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}
struct WBLT {
    int val;
    int size;
    WBLT *lc, *rc;
    WBLT() {
        val = 0;
        size = 0;
        lc = rc = NULL;
    }
    WBLT(int a, int b, WBLT* c, WBLT* d) {
        val = a;
        size = b;
        lc = c;
        rc = c;
    }
};
inline WBLT* newnode(int a, int b, WBLT* c, WBLT* d) {
    return &(*(WBLT*)malloc(sizeof(WBLT*)) = WBLT(a, b, c, d));
}
inline WBLT* merge(WBLT* a, WBLT* b) {
    return newnode(b->val, a->size + b->size, a, b);
}
inline void left_rotate(WBLT* a) {
    a->lc = merge(a->lc, a->rc->lc);
    delete a->rc;
    a->rc = a->rc->rc;
}
inline void right_rotate(WBLT* a) {
    a->rc = merge(a->rc, a->lc->rc);
    delete a->lc;
    a->lc = a->lc->lc;
}
const int radio = 5;
inline void maintain(WBLT* a) {
    if(a->lc==NULL)
        return;
    if (a->lc->size > a->rc->size * radio)
        right_rotate(a);
    else if (a->rc->size > a->lc->size * radio)
        left_rotate(a);
}
inline void pushup(WBLT* a) {
    if (a->rc == NULL) {
        a->rc = a->lc;
        a->lc = NULL;
    }
    a->val = a->rc->val;
    a->size = a->rc->size;
    if (a->lc != NULL)
        a->size += a->lc->size;
}
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
void ins(WBLT* a, int val) {
    if (a->size == 1) {
        a->lc = newnode(min(a->val, val), 1, NULL, NULL);
        a->rc = newnode(max(a->val, val), 1, NULL, NULL);
        pushup(a);
        maintain(a);
        return;
    }
    ins(a->val > val ? a->lc : a->rc, val);
    pushup(a);
    maintain(a);
}
void del(WBLT* a, WBLT* fa, WBLT* bro, int val) {
    if (a->size == 1) {
        *fa = WBLT(bro->val, bro->size, NULL, bro);
        free(a);
        return;
    }
    if (a->val > val)
        del(a->lc, a, a->rc, val);
    else
        del(a->rc, a, a->lc, val);
    pushup(a);
    maintain(a);
}
int rank(WBLT* a, int val) {
    if (a->val == val)
        return a->size;
    if (a->val > val)
        return rank(a->lc, val);
    return rank(a->rc, val) + a->lc->size;
}
int value(WBLT* a, int rk) {
    if (a->size == rk)
        return a->val;
    if (a->lc->size > rk)
        return rank(a->lc, rk);
    return rank(a->rc, rk - a->lc->size);
}
int main() {
    int n = read();
    int m = read();
    WBLT* root = newnode(2147483647, 1, NULL, NULL);
    while (n--) {
        int x = read();
        printf("%d", x);
        ins(root, x);
    }
    int lastans = 0, ans = 0;
    while (m--) {
        int op, x;
        op = read();
        x = read() ^ lastans;
        switch (op) {
            case 1: {
                ins(root, x);
                break;
            }
            case 2: {
                del(root, NULL, NULL, x);
                break;
            }
            case 3: {
                lastans = rank(root, x);
                break;
            }
            case 4: {
                lastans = value(root, x);
                break;
            }
            case 5: {
                lastans = value(root, rank(root, x) - 1);
                break;
            }
            default:
                lastans = value(root, rank(root, x) + 1);
        }
        if (op != 1 && op != 2)
            ans ^= lastans;
    }
    printf("%d", ans);
    return 0;
}

目前改成这样了，但还是有问题