< tombo_さんのAI生成コード置き場

persistent_lazy_segtree

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

/**
 * Persistent Lazy Segment Tree with range copy
 * ACL-like interface:
 *   S, op, e, F, mapping(F,S,len), composition, id
 */
template <
    class S, S (*op)(S, S), S (*e)(),
    class F, S (*mapping)(F, S, int),
    F (*composition)(F, F), F (*id)()
>
struct persistent_lazy_segtree {
    struct Node {
        S val;
        F lz;
        Node* l;
        Node* r;
        Node(const S& v = e(), const F& f = id(), Node* l_ = nullptr, Node* r_ = nullptr)
            : val(v), lz(f), l(l_), r(r_) {}
    };

    int n;

    persistent_lazy_segtree(int n_) : n(n_) {}

    // ---- utils ----
    S get(Node* t) const { return t ? t->val : e(); }

    Node* ensure(Node* t) { return t ? t : new Node(); }

    Node* apply(Node* t, const F& f, int len) {
        t = ensure(t);
        Node* nt = new Node(*t);
        nt->val = mapping(f, nt->val, len);
        nt->lz = composition(f, nt->lz);
        return nt;
    }

    Node* push(Node* t, int len) {
        if (!t || t->lz == id()) return t;
        int half = len >> 1;
        Node* nt = new Node(*t);
        nt->l = apply(nt->l, t->lz, half);
        nt->r = apply(nt->r, t->lz, len - half);
        nt->lz = id();
        return nt;
    }

    Node* update(Node* t) {
        t->val = op(get(t->l), get(t->r));
        return t;
    }

    // ---- build ----
    Node* build(const vector<S>& v) { return build(0, n, v); }
    Node* build(int l, int r, const vector<S>& v) {
        if (l + 1 == r) return new Node(v[l], id());
        int m = (l + r) >> 1;
        Node* nl = build(l, m, v);
        Node* nr = build(m, r, v);
        return new Node(op(get(nl), get(nr)), id(), nl, nr);
    }

    // ---- range apply [l, r) ----
    Node* apply(Node* t, int l, int r, const F& f) {
        return apply(t, 0, n, l, r, f);
    }
    Node* apply(Node* t, int nl, int nr, int l, int r, const F& f) {
        if (r <= nl || nr <= l) return t;
        if (!t) t = new Node();
        if (l <= nl && nr <= r) return apply(t, f, nr - nl);
        t = push(t, nr - nl);
        int m = (nl + nr) >> 1;
        Node* nlch = apply(t->l, nl, m, l, r, f);
        Node* nrch = apply(t->r, m, nr, l, r, f);
        Node* nt = new Node(*t);
        nt->l = nlch; nt->r = nrch;
        return update(nt);
    }

    // ---- range copy: replace [l, r) of tk with ts ----
    Node* range_copy(Node* tk, Node* ts, int l, int r) {
        return range_copy(tk, ts, 0, n, l, r);
    }
    Node* range_copy(Node* tk, Node* ts, int nl, int nr, int l, int r) {
        if (r <= nl || nr <= l) return tk;
        if (l <= nl && nr <= r) return ts; // share
        tk = ensure(tk);
        ts = ensure(ts);
        tk = push(tk, nr - nl);
        ts = push(ts, nr - nl);
        int m = (nl + nr) >> 1;
        Node* nlch = range_copy(tk->l, ts->l, nl, m, l, r);
        Node* nrch = range_copy(tk->r, ts->r, m, nr, l, r);
        Node* nt = new Node(*tk);
        nt->l = nlch; nt->r = nrch;
        return update(nt);
    }

    // ---- range prod [l, r) ----
    S prod(Node* t, int l, int r) { return prod(t, 0, n, l, r); }
    S prod(Node* t, int nl, int nr, int l, int r) {
        if (!t || r <= nl || nr <= l) return e();
        if (l <= nl && nr <= r) return t->val;
        t = push(t, nr - nl);
        int m = (nl + nr) >> 1;
        return op(prod(t->l, nl, m, l, r),
                  prod(t->r, m, nr, l, r));
    }

    // ---- point set ----
    Node* set(Node* t, int pos, const S& x) {
        return set(t, 0, n, pos, x);
    }
    Node* set(Node* t, int nl, int nr, int pos, const S& x) {
        if (!t) t = new Node();
        if (nr - nl == 1) return new Node(x, id());
        t = push(t, nr - nl);
        int m = (nl + nr) >> 1;
        Node* nlch = (pos < m) ? set(t->l, nl, m, pos, x) : t->l;
        Node* nrch = (pos < m) ? t->r : set(t->r, m, nr, pos, x);
        Node* nt = new Node(*t);
        nt->l = nlch; nt->r = nrch;
        return update(nt);
    }

    // ---- point get ----
    S get(Node* t, int pos) { return get(t, 0, n, pos); }
    S get(Node* t, int nl, int nr, int pos) {
        if (!t) return e();
        if (nr - nl == 1) return t->val;
        t = push(t, nr - nl);
        int m = (nl + nr) >> 1;
        if (pos < m) return get(t->l, nl, m, pos);
        else return get(t->r, m, nr, pos);
    }
};