WA+TLE自闭了,求大佬。。。

@dimension_missing 2019-02-08 23:12 回复
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 100000 + 7;
const int INF = 2147483647;

struct splay {
    int val[N], siz[N], cnt[N], kid[N][2], fa[N];
    int root, ct, buf[N], bt;
    splay();
    inline void update(int p);
    inline int dic(int p);
    void out(int p);
    inline void spin(int p);
    inline void spaly(int p);
    inline int lower(int x);
    inline int upper(int x);
    inline int mini(int p);
    inline void push(int x);
    inline void pop(int x);
    inline int kth(int k);
    inline int rank(int x);
} spt;

int q;

int main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    scanf("%d", &q);
    for (int opt, x, p; q; --q) {
        scanf("%d%d", &opt, &x);
        if (opt == 1) spt.push(x);
        else if (opt == 2) spt.pop(x);
        else if (opt == 3) printf("%d\n", spt.rank(x));
        else if (opt == 4) printf("%d\n", spt.kth(x));
        else if (opt == 5) printf("%d\n", spt.lower(x));
        else if (opt == 6) printf("%d\n", spt.upper(x));
        else spt.out(spt.root), printf("\n");
    }
    return 0;
}

splay::splay() {
    root = 1, ct = 2;
    val[1] = -INF, siz[1] = 2, cnt[1] = 1, kid[1][0] = 0, kid[1][1] = 2, fa[1] = 0;
    val[2] = INF, siz[2] = 1, cnt[2] = 1, kid[2][0] = kid[2][1] = 0, fa[2] = 1;
}

inline void splay::update(int p) {
    siz[p] = cnt[p] + siz[kid[p][0]] + siz[kid[p][1]];
}

inline int splay::dic(int p) {
    return kid[fa[p]][1] == p;
}

void splay::out(int p) {
    if (!p) return;
    out(kid[p][0]);
    for (int i = 1; i <= cnt[p]; ++i) printf("%d ", val[p]);
    out(kid[p][1]);
}

inline void splay::spin(int p) {
    int f = fa[p], d = dic(p);
    kid[f][d] = kid[p][!d], fa[kid[p][!d]] = f;
    kid[fa[f]][dic(f)] = p, fa[p] = fa[f];
    kid[p][!d] = f, fa[f] = p;
    update(f);
    update(p);
}

inline void splay::spaly(int p) {
    while (fa[p] && fa[fa[p]])
        spin((dic(p) ^ dic(fa[p])) ? p : fa[p]), spin(p);
    if (fa[p]) spin(p);
    root = p;
}

inline int splay::upper(int x) {
    int g = 2, p = root;
    while (p) g = (x < val[p]) ? p : g, p = kid[p][x >= val[p]];
    spaly(g);
    return val[g];
}

inline int splay::lower(int x) {
    int g = 1, p = root;
    while (p) g = (x > val[p]) ? p : g, p = kid[p][x > val[p]];
    spaly(g);
    return val[g];
}

inline int splay::mini(int p) {
    while (kid[p][0]) p = kid[p][0];
    return p;
}

inline void splay::push(int x) {
    lower(x);
    int p = mini(kid[root][1]), g;
    if (x == val[p]) ++cnt[p], ++siz[p], spaly(p);
    else {
        kid[p][0] = g = (bt ? buf[bt--] : ++ct);
        val[g] = x, siz[g] = cnt[g] = 1, kid[g][0] = kid[g][1] = 0, fa[g] = p;
//      (g == root) ? update(g) : spaly(g);
        spaly(g);
    }
}

inline void splay::pop(int x) {
    lower(x);
    int p = mini(kid[root][1]), g;
    if (x != val[p]) return;
    g = fa[p];
    if (cnt[p] > 1) --cnt[p];
    else kid[g][dic(p)] = kid[p][1], fa[kid[p][1]] = g, buf[++bt] = p;
    (g == root) ? update(g) : spaly(g);
}

inline int splay::kth(int x) {
    x = max(x + 1, 1); x = min(x, siz[root]);
    int p = root;
    while (p)
        if (x <= siz[kid[p][0]]) p = kid[p][0];
        else if (x <= siz[kid[p][0]] + cnt[p]) break;
        else x -= siz[kid[p][0]] + cnt[p], p = kid[p][1];
    spaly(p);
    return val[p];
}

inline int splay::rank(int x) {
    lower(x);
    return siz[kid[root][0]] + cnt[root];
}
@dimension_missing 2019-02-08 23:13 回复

val 数值大小

cnt 重复次数

siz 子树大小

kid/fa 孩子/父亲

buf是节点回收

@ZYyboT 2019-02-08 23:59 回复

慢慢调,相信奇迹(由于代码不是指针实现的所以没有看的欲望)

@skicean 2019-02-09 00:11 回复

哇,您太强了我没有资格帮你看啊qwq