RT 做了道题 树状数组+离散化被卡了 被迫回来学 treap

#include <bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f
using namespace std;

class Treap {
  private:
    int val[N], key[N], size[N], count[N];
    int ch[N][2];
    int total;
    #define v(x) val[x]
    #define k(x) key[x]
    #define s(x) size[x]
    #define cnt(x) count[x]
    #define c(x, d) ch[x][d]
    void pushup(int x) {
        s(x) = s(c(x, 0)) + s(c(x, 1));
    }
    void rotate(int &x, int d) {
        int temp = c(x, d ^ 1);
        c(x, d ^ 1) = c(temp, d);
        c(temp, d) = x;
        pushup(x);
        pushup(temp);
        x = temp;
    }
    int create(int v) {
        total++;
        v(total) = v;
        k(total) = rand();
        s(total) = cnt(total) = 1;
        return total;
    }
  public:
    int root;
    void build() {
        root = create(-INF);
        c(root, 1) = create(INF);
        pushup(root);
    }
    void ins(int &x, int v) {
        cout << "INS " << x << " " << v << endl;;
        if (!x) {
            cout << "CRT NODE " << x << endl;
            x = create(v);
            return;
        }
        if (v == v(x)) {
            cnt(x)++;
            return;
        }
        int d = (v >= v(x));
        ins(c(x, d), v);
        if (k(x) < k(c(x, d))) {
            rotate(x, d ^ 1);
        }
        pushup(x);
    }
    void del(int &x, int v) {
        if (!x) return;
        if (v == v(x)) {
            if (cnt(x) > 1) cnt(x)--;
            else if (s(x) == 0) x = 0;
            else {
                int d = !c(x, 1) || v(c(x, 0)) > v(c(x, 1));
                rotate(x, d);
                del(c(x, 2), v);
            }
        } else {
            int d = v > v(x);
            del(c(x, d), v);
        }
        pushup(x);
    }
    int v2k(int x, int v) {
        if (!x) return -2;
        if (v == v(x)) return s(c(x, 0)) + 1;
        else if (v < v(x)) return v2k(c(x, 0), v);
        else return s(c(x, 0)) + cnt(x) + v2k(c(x, 1), v);
    }
    int k2v(int x, int k) {
        if (!x) return INF;
        cout << "K2V " << x << " " << k << " " << s(c(x, 0)) << endl;
        if (k <= s(c(x, 0))) return k2v(c(x, 0), k);
        else if (k <= s(c(x, 0)) + cnt(x)) return v(x);
        else return k2v(c(x, 1), k - s(c(x, 0)) - cnt(x));
    }
    /*
    int k2v(int x,int k){
	    if (!x) return INF;
	    if (k <= s[c(x, 0)]) return k2v(c(x, 0),k);
		else if(k <= s(c(x, 0)) + cnt[x]) return v[x];
	    else return k2v(ch[x][1], k - s[c(x, 0)] - cnt[x]);
	}
    */
    int near(int x, int d) {
        int r = root, near;
        while (r) {
            if (v(r) > x ^ d) {
                near = v(r);
                r = c(r, d ^ 1);
            } else r = c(r, d);
        }
        return near;
    }
};

Treap t;
int n, opt, x;

int main() {
    cin >> n;
    t.build();
    for (int i = 1; i <= n; i++) {
        cin >> opt >> x;
        if (opt == 1) t.ins(t.root, x);
        else if (opt == 2) t.del(t.root, x);
        else if (opt == 3) cout << t.v2k(t.root, x) - 1 << endl;
        else if (opt == 4) cout << t.k2v(t.root, x + 1) << endl;
        else if (opt == 5) cout << t.near(x, 0) << endl;
        else if (opt == 6) cout << t.near(x, 1) << endl;
    }
}

提供调试信息

input:

2
1 1
4 1

output:

INS 1 1
INS 2 1
INS 0 1
CRT NODE 0
K2V 2 2 1
4144959 (0x3f3f3f)

solution-output:

INS 1 1
INS 2 1
INS 0 1
CRT NODE 0
K2V 2 2
K2V 1 2
K2V 3 1
1