Treap 板子 40pts 求助！

GI录像机 @ 2022-06-10 17:13:36

by GI录像机 @ 2022-06-10 17:13:50

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
const int N = 2e6 + 10, INF = 1145141919810;
int num[N], son[N][2], tot, v[N], siz[N], rd[N], root, last, n, m, ans = 0;
void write(int x) {
    ans ^= x;
    last = x;
}
void pushup(int pos) {
    siz[pos] = siz[son[pos][0]] + siz[son[pos][1]] + num[pos];
}
void rotate(int &pos, int d) {
    int tmp = son[pos][d ^ 1];
    son[pos][d ^ 1] = son[tmp][d];
    son[tmp][d] = pos;
    pushup(pos);
    pushup(tmp);
    pos = tmp;
}
void ins(int &pos, int k) {
    if (!pos) {
        pos = ++tot;
        num[pos] = siz[pos] = 1;
        v[pos] = k;
        rd[pos] = rand();
        return;
    }
    if (v[pos] == k) {
        num[pos]++;
        siz[pos]++;
        return;
    }
    int d = (k > v[pos]);
    ins(son[pos][d], k);
    if (rd[pos] < rd[son[pos][d]])rotate(pos, d ^ 1);
    pushup(pos);
}
void del(int &pos, int k) {
    if (!pos)return;
    else if (v[pos] != k)del(son[pos][(int)(k > v[pos])], k);
    else {
        if (!son[pos][0] && !son[pos][1]) {
            num[pos]--;
            siz[pos]--;
            if (!num[pos])pos = 0;
        } else if (!son[pos][0] && son[pos][1]) {
            rotate(pos, 0);
            del(son[pos][0], k);
        } else if (son[pos][0] && !son[pos][1]) {
            rotate(pos, 1);
            del(son[pos][1], k);
        } else {
            int d = (rd[son[pos][0]] > rd[son[pos][1]]);
            rotate(pos, d);
            del(son[pos][d], k);
        }
    }
    pushup(pos);
}
int ran(int pos, int k) {
    if (!pos)return 0;
    if (v[pos] == k)return siz[son[pos][0]] + 1;
    if (v[pos] > k)return ran(son[pos][0], k);
    if (v[pos] < k) return num[pos] + siz[son[pos][0]] + ran(son[pos][1], k);
}
int fin(int pos, int k) {
    if (!pos)return -1;
    if (siz[son[pos][0]] >= k)return fin(son[pos][0], k);
    else if (siz[son[pos][0]] + num[pos] >= k)return v[pos];
    else return fin(son[pos][1], k - siz[son[pos][0]] - num[pos]);
}
int pre(int pos, int k) {
    if (!pos)return -INF;
    if (v[pos] >= k)return pre(son[pos][0], k);
    else return max(pre(son[pos][1], k), v[pos]);
}
int suc(int pos, int k) {
    if (!pos)return INF;
    if (v[pos] <= k)return suc(son[pos][1], k);
    else return min(suc(son[pos][0], k), v[pos]);
}
signed main() {
    n = read();
    m = read();
    ins(root, 1145141919810);
    for (int i = 1; i <= n; i++)ins(root, read());
    while (m--) {
        int opt = read(), k = read();
        k ^= last;
        if (opt == 1)ins(root, k);
        else if (opt == 2)del(root, k);
        else if (opt == 3)write(ran(root, k) + 1);
        else if (opt == 4) {
            if (fin(root, k) == -1)k = pre(root, k);
            write(fin(root, k));
        } else if (opt == 5)write(pre(root, k));
        else write(suc(root, k));
    }
    cout << ans;
    return 0;
}

by Grimgod @ 2022-06-11 14:24:41

为什么不写fhq?

by GI录像机 @ 2022-06-12 16:47:23

@grimgod 不会写啊

Dalao 帮忙看看呗

by GI录像机 @ 2022-06-12 16:55:45

超，wssb，k 不是数是排名

by GI录像机 @ 2022-06-12 17:32:54

修改后：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e6 + 10, INF = 1145141919810;
int num[N], son[N][2], tot, v[N], siz[N], rd[N], root, last, n, m, ans = 0;
void handle(int x) {
    ans ^= x;
    last = x;
}
void pushup(int pos) {
    siz[pos] = siz[son[pos][0]] + siz[son[pos][1]] + num[pos];
}
void rotate(int &pos, int d) {
    int tmp = son[pos][d ^ 1];
    son[pos][d ^ 1] = son[tmp][d];
    son[tmp][d] = pos;
    pushup(pos);
    pushup(tmp);
    pos = tmp;
}
void ins(int &pos, int k) {
    if (!pos) {
        pos = ++tot;
        num[pos] = siz[pos] = 1;
        v[pos] = k;
        rd[pos] = rand();
        return;
    }
    if (v[pos] == k) {
        num[pos]++;
        siz[pos]++;
        return;
    }
    int d = (k > v[pos]);
    ins(son[pos][d], k);
    if (rd[pos] < rd[son[pos][d]])rotate(pos, d ^ 1);
    pushup(pos);
}
void del(int &pos, int k) {
    if (!pos)return;
    else if (v[pos] != k)del(son[pos][(int)(k > v[pos])], k);
    else {
        if (!son[pos][0] && !son[pos][1]) {
            num[pos]--;
            siz[pos]--;
            if (!num[pos])pos = 0;
        } else if (!son[pos][0] && son[pos][1]) {
            rotate(pos, 0);
            del(son[pos][0], k);
        } else if (son[pos][0] && !son[pos][1]) {
            rotate(pos, 1);
            del(son[pos][1], k);
        } else {
            int d = (rd[son[pos][0]] > rd[son[pos][1]]);
            rotate(pos, d);
            del(son[pos][d], k);
        }
    }
    pushup(pos);
}
int ran(int pos, int k) {
    if (!pos)return 0;
    if (v[pos] == k)return siz[son[pos][0]] + 1;
    if (v[pos] > k)return ran(son[pos][0], k);
    if (v[pos] < k) return num[pos] + siz[son[pos][0]] + ran(son[pos][1], k);
}
int fin(int pos, int k) {
    if (!pos)return 1;
    if (siz[son[pos][0]] >= k)return fin(son[pos][0], k);
    else if (siz[son[pos][0]] + num[pos] >= k)return v[pos];
    else return fin(son[pos][1], k - siz[son[pos][0]] - num[pos]);
}
int pre(int pos, int k) {
    if (!pos)return -INF;
    if (v[pos] >= k)return pre(son[pos][0], k);
    else return max(pre(son[pos][1], k), v[pos]);
}
int suc(int pos, int k) {
    if (!pos)return INF;
    if (v[pos] <= k)return suc(son[pos][1], k);
    else return min(suc(son[pos][0], k), v[pos]);
}
signed main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)ins(root, read());
    while (m--) {
        int opt = read(), k = read();
        k ^= last;
        if (opt == 1)ins(root, k);
        else if (opt == 2)del(root, k);
        else if (opt == 3)handle(ran(root, k) + 1);
        else if (opt == 4)handle(fin(root, k));
        else if (opt == 5)handle(pre(root, k));
        else handle(suc(root, k));
    }
    write(ans);
    return 0;
}

by huangkx @ 2022-06-22 10:44:18

@GI录像机 让我想起了我曾经写的 Treap，然而至今我都没调出来 QwQ

by GI录像机 @ 2022-06-22 12:35:03

@huangkx 同

by huangkx @ 2022-06-22 13:55:13

@GI录像机 然后我就气愤地去学了fhq （雾