（常数贼大的）线段树套平衡树板子

__ryp__ · 2024-05-10 20:12:11 · 个人记录

const int N = 1e5 + 10, oo = 2147483647;
int fa[N << 6], son[N << 6][2], siz[N << 6], cntq[N << 6], val[N << 6], rt[4 * N], cnt = 1, z[N], n;

namespace splay {
static inline void maintain (int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + cntq[x]; }
static inline int get (int x) { return x == son[fa[x]][1]; }
static inline int compare (int f, int k) { return k > val[f]; }
static inline void rotate (int x)
{
    int y = fa[x], z = fa[y], p = get (x);
    son[y][p] = son[x][p ^ 1];
    if (son[x][p ^ 1]) fa[son[x][p ^ 1]] = y;
    fa[fa[son[x][p ^ 1] = y] = x] = z;
    if (z) son[z][y == son[z][1]] = x;
    maintain (y), maintain (x);
}

static inline int splay (int &rt, int x, int t = 0)
{
    for (int f = fa[x]; (f = fa[x]) != t; rotate (x))
        if (fa[f] != t) rotate (get (x) == get (f) ? f : x);
    return t ? x : rt = x;
}

static inline int insert_at (int f, int k)
{
    siz[cnt] = cntq[cnt] = 1, val[cnt] = k, fa[cnt] = f;
    if (f) son[f][compare (f, k)] = cnt;
    return cnt++;
}

static inline int insert (int &rt, int k)
{
    int f = rt, last = 0;
    if (!f) return rt = insert_at (0, k);
    while (f && val[f] != k) last = f, f = son[f][compare (f, k)];
    if (f && val[f] == k) return cntq[f]++, splay (rt, f);
    else return f = insert_at (last, k), maintain (last), splay (rt, f);
}

static inline int find (int &rt, int k)
{
    int f = rt;
    if (!f) return 0;
    while (val[f] != k && son[f][compare (f, k)]) f = son[f][compare (f, k)];
    return splay (rt, f);
}

static inline int merge (int &rt, int x, int y)
{
    int f = x;
    if (!x || !y) return x + y;
    while (son[f][1]) f = son[f][1];
    son[splay (rt, f, fa[x])][1] = y;
    if (y) fa[y] = f;
    return f;
}

static inline int remove (int &rt, int k)
{
    int f = find (rt, k), x;
    if (cntq[f] > 1) return cntq[f]--, splay (rt, f);
    if ((x = merge (rt, son[f][0], son[f][1]))) fa[x] = 0;
    return rt = x;
}

static inline int qnxt (int &rt, int k)
{
    int f = son[find (rt, k)][1];
    if (val[rt] > k) return rt;
    while (son[f][0]) f = son[f][0];
    return splay (rt, f);
}

static inline int qpre (int &rt, int k)
{
    int f = son[find (rt, k)][0];
    if (val[rt] < k) return rt;
    while (son[f][1]) f = son[f][1];
    return splay (rt, f);
}

static inline int qrank (int &rt, int k) { return siz[son[find (rt, k)][0]] + (val[rt] < k ? cntq[rt] : 0); }
}

namespace segtree {
static inline void build (int i, int x, int y)
{
    int mid = (x + y) / 2;
    splay::insert (rt[i], oo), splay::insert (rt[i], -oo);
    if (x != y) build (i * 2, x, mid), build (i * 2 + 1, mid + 1, y);
}

static inline void insert (int i, int x, int y, int p, int k)
{
    int mid = (x + y) / 2;
    splay::insert (rt[i], k);
    if (x == y) return;
    if (p <= mid) insert (i * 2, x, mid, p, k);
    else insert (i * 2 + 1, mid + 1, y, p, k);
}

static inline int qrank (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) / 2, res = 0;
    if (l <= x && y <= r) return splay::qrank (rt[i], k) - 1;
    if (l <= mid) res = qrank (i * 2, x, mid, l, r, k);
    if (r > mid) res += qrank (i * 2 + 1, mid + 1, y, l, r, k);
    return res;
}

static inline void upd (int i, int x, int y, int p, int k)
{
    int mid = (x + y) / 2;
    splay::remove (rt[i], z[p]), splay::insert (rt[i], k);
    if (x == y) return z[p] = k, void ();
    if (p <= mid) upd (i * 2, x, mid, p, k);
    else upd (i * 2 + 1, mid + 1, y, p, k);
}

static inline int qpre (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) / 2, res = -oo;
    if (l <= x && y <= r) return val[splay::qpre (rt[i], k)];
    if (l <= mid) res = qpre (i * 2, x, mid, l, r, k);
    if (r > mid) res = max (res, qpre (i * 2 + 1, mid + 1, y, l, r, k));
    return res;
}

static inline int qnxt (int i, int x, int y, int l, int r, int k)
{
    int mid = (x + y) / 2, res = oo;
    if (l <= x && y <= r) return val[splay::qnxt (rt[i], k)];
    if (l <= mid) res = qnxt (i * 2, x, mid, l, r, k);
    if (r > mid) res = min (res, qnxt (i * 2 + 1, mid + 1, y, l, r, k));
    return res;
}

static inline void build (void) { build (1, 1, n); }
static inline void insert (int p, int k) { insert (1, 1, n, p, k); }
static inline int qrank (int l, int r, int k) { return qrank (1, 1, n, l, r, k); }
static inline void upd (int p, int k) { upd (1, 1, n, p, k); }
static inline int qpre (int l, int r, int k) { return qpre (1, 1, n, l, r, k); }
static inline int qnxt (int l, int r, int k) { return qnxt (1, 1, n, l, r, k); }
static inline int kth (int x, int y, int k)
{
    int l = 0, r = 1e9, mid, ans = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        if (qrank (x, y, mid) + 1 <= k) l = (ans = mid) + 1;
        else r = mid - 1;
    }
    return ans;
}
}