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

dynamic_lazy_segtree

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

// Dynamic Lazy Segment Tree (implicit)
// template params: 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 dynamic_lazy_segtree {
    struct Node {
        S val;
        F lz;
        Node* l;
        Node* r;
        Node(const S& v, const F& f) : val(v), lz(f), l(nullptr), r(nullptr) {}
    };

    int n;
    Node* root;

    dynamic_lazy_segtree(int n_) : n(n_), root(nullptr) {}

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

    void apply(Node*& t, const F& f, int len) {
        if (!t) t = new Node(e(), id());
        t->val = mapping(f, t->val, len);
        t->lz = composition(f, t->lz);
    }

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

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

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

    // range prod [l, r)
    S prod(int l, int r) { return prod(root, 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;
        push(t, nr - nl);
        int mid = (nl + nr) >> 1;
        return op(prod(t->l, nl, mid, l, r),
                  prod(t->r, mid, nr, l, r));
    }

    // point set
    void set(int pos, const S& x) { set(root, 0, n, pos, x); }
    void set(Node*& t, int nl, int nr, int pos, const S& x) {
        if (!t) t = new Node(e(), id());
        if (nr - nl == 1) {
            t->val = x;
            t->lz = id();
            return;
        }
        push(t, nr - nl);
        int mid = (nl + nr) >> 1;
        if (pos < mid) set(t->l, nl, mid, pos, x);
        else set(t->r, mid, nr, pos, x);
        update(t);
    }

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