Halc's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

Lazy Segment Tree
(DataStructure/LazySegmentTree.hpp)

• View this file on GitHub
• Last update: 2024-05-15 20:31:29+09:00
• Include: #include "DataStructure/LazySegmentTree.hpp"

関数の設定

struct M {
    using T;
    using F;
    static T op(T x, T y) {}
    static inline T e;
    static T mapp(F f, T x) {}
    static F comp(F f, F g) {}
    static inline F id;
};

• T: モノイドの型です。
• F: 遅延の型です。
• T op(T x,T y): 演算です。モノイドであることを要求します。
• T e: 単位元です。
• T mapp(F f,T x): 要素に遅延を伝える演算です。
• F comp(F f,F g): 遅延を合成する演算です。fが新しい方であることを意識するとよいかもしれません。
• F id: 遅延の単位元です。

Verified with

• Verify/verify-aoj/2667.test.cpp
• Verify/verify-yosupo-datastructure/range_affine_point_get.test.cpp
• Verify/verify-yosupo-datastructure/range_affine_range_sum.test.cpp
• Verify/verify-yuki/235.test.cpp
• Verify/verify-yuki/900.test.cpp

Code

#pragma once
#include <bit>
#include <cstdint>
#include <queue>
#include <stack>
#include <vector>
template <class M>
struct LazySegmentTree {
    using T = typename M::T;
    using F = typename M::F;
    int32_t siz;
    std::vector<T> tree;
    std::vector<F> del;
    LazySegmentTree(int32_t sz) {
        siz = sz;
        tree = std::vector<T>(siz << 1, M::e);
        del = std::vector<F>(siz << 1, M::id);
    }
    LazySegmentTree(std::vector<T> def) {
        siz = def.size();
        tree = std::vector<T>(siz << 1, M::e);
        del = std::vector<F>(siz << 1, M::id);
        for (int32_t i = 0; i < siz; i++) {
            tree[i + siz] = def[i];
        }
        for (int32_t i = siz - 1; i > 0; i--) {
            tree[i] = M::op(tree[i << 1], tree[(i << 1) + 1]);
        }
    }
    inline T _get(int32_t pos) { return tree[pos]; }
    void _calc(int32_t p) {
        p >>= 1;
        while (p > 0) {
            tree[p] = M::op(_get(p << 1), _get((p << 1) + 1));
            p >>= 1;
        }
    }
    inline void _del_segment(int32_t p) {
        tree[p << 1] = M::mapp(del[p], tree[p << 1]);
        del[p << 1] = M::comp(del[p], del[p << 1]);
        tree[(p << 1) + 1] = M::mapp(del[p], tree[(p << 1) + 1]);
        del[(p << 1) + 1] = M::comp(del[p], del[(p << 1) + 1]);
        del[p] = M::id;
    }
    void _delay(int32_t p) {
        int32_t length = 32 - std::countl_zero((uint32_t)p);
        for (int32_t i = length - 1; i >= 1; i--) {
            _del_segment(p >> i);
        }
    }
    void set(int32_t p, T v) {
        p += siz;
        _delay(p);
        tree[p] = v;
        del[p] = M::id;
        _calc(p);
    }
    T get(int32_t p) {
        _delay(p + siz);
        return _get(p + siz);
    }
    void apply(int32_t lf, int32_t ri, F f) {
        lf += siz;
        ri += siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        while (lf < ri) {
            if (lf & 1) {
                tree[lf] = M::mapp(f, tree[lf]);
                del[lf] = M::comp(f, del[lf]);
                lf++;
            }
            if (ri & 1) {
                ri--;
                tree[ri] = M::mapp(f, tree[ri]);
                del[ri] = M::comp(f, del[ri]);
            }
            lf >>= 1;
            ri >>= 1;
        }
        _calc(dl);
        _calc(dr - 1);
    }
    T prod(int32_t lf, int32_t ri) {
        lf += siz;
        ri += siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        T rel = M::e;
        T rer = M::e;
        while (lf < ri) {
            if (lf & 1) {
                rel = M::op(rel, _get(lf));
                lf++;
            }
            if (ri & 1) {
                ri--;
                rer = M::op(_get(ri), rer);
            }
            lf >>= 1;
            ri >>= 1;
        }
        return M::op(rel, rer);
    }
    template <class F>
    int32_t max_right(int32_t lf, F f) {
        lf += siz;
        int32_t ri = siz << 1;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        std::queue<int32_t> lfp;
        std::stack<int32_t> rip;
        while (lf < ri) {
            if (lf & 1) {
                lfp.push(lf);
                lf++;
            }
            if (ri & 1) {
                ri--;
                rip.push(ri);
            }
            lf >>= 1;
            ri >>= 1;
        }
        T val = M::e;
        while (!lfp.empty()) {
            int32_t i = lfp.front();
            lfp.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    if (f(M::op(val, _get(i)))) {
                        val = M::op(val, _get(i));
                        i++;
                    }
                }
                return i - siz;
            }
            val = M::op(val, _get(i));
        }
        while (!rip.empty()) {
            int32_t i = rip.top();
            rip.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    if (f(M::op(val, _get(i)))) {
                        val = M::op(val, _get(i));
                        i++;
                    }
                }
                return i - siz;
            }
            val = M::op(val, _get(i));
        }
        return siz;
    }
    template <class F>
    int32_t min_left(int32_t ri, F f) {
        ri += siz;
        int32_t lf = siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        std::queue<int32_t> rip;
        std::stack<int32_t> lfp;
        while (lf < ri) {
            if (lf & 1) {
                lfp.push(lf);
                lf++;
            }
            if (ri & 1) {
                ri--;
                rip.push(ri);
            }
            lf >>= 1;
            ri >>= 1;
        }
        T val = M::e;
        while (!rip.empty()) {
            int32_t i = rip.front();
            rip.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    i++;
                    if (f(M::op(_get(i), val))) {
                        val = M::op(_get(i), val);
                        i--;
                    }
                }
                return i - siz + 1;
            }
            val = M::op(_get(i), val);
        }
        while (!lfp.empty()) {
            int32_t i = lfp.top();
            lfp.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    i++;
                    if (f(M::op(_get(i), val))) {
                        val = M::op(_get(i), val);
                        i--;
                    }
                }
                return i - siz + 1;
            }
            val = M::op(_get(i), val);
        }
        return 0;
    }
    int32_t size() { return siz; }
};

#line 2 "DataStructure/LazySegmentTree.hpp"
#include <bit>
#include <cstdint>
#include <queue>
#include <stack>
#include <vector>
template <class M>
struct LazySegmentTree {
    using T = typename M::T;
    using F = typename M::F;
    int32_t siz;
    std::vector<T> tree;
    std::vector<F> del;
    LazySegmentTree(int32_t sz) {
        siz = sz;
        tree = std::vector<T>(siz << 1, M::e);
        del = std::vector<F>(siz << 1, M::id);
    }
    LazySegmentTree(std::vector<T> def) {
        siz = def.size();
        tree = std::vector<T>(siz << 1, M::e);
        del = std::vector<F>(siz << 1, M::id);
        for (int32_t i = 0; i < siz; i++) {
            tree[i + siz] = def[i];
        }
        for (int32_t i = siz - 1; i > 0; i--) {
            tree[i] = M::op(tree[i << 1], tree[(i << 1) + 1]);
        }
    }
    inline T _get(int32_t pos) { return tree[pos]; }
    void _calc(int32_t p) {
        p >>= 1;
        while (p > 0) {
            tree[p] = M::op(_get(p << 1), _get((p << 1) + 1));
            p >>= 1;
        }
    }
    inline void _del_segment(int32_t p) {
        tree[p << 1] = M::mapp(del[p], tree[p << 1]);
        del[p << 1] = M::comp(del[p], del[p << 1]);
        tree[(p << 1) + 1] = M::mapp(del[p], tree[(p << 1) + 1]);
        del[(p << 1) + 1] = M::comp(del[p], del[(p << 1) + 1]);
        del[p] = M::id;
    }
    void _delay(int32_t p) {
        int32_t length = 32 - std::countl_zero((uint32_t)p);
        for (int32_t i = length - 1; i >= 1; i--) {
            _del_segment(p >> i);
        }
    }
    void set(int32_t p, T v) {
        p += siz;
        _delay(p);
        tree[p] = v;
        del[p] = M::id;
        _calc(p);
    }
    T get(int32_t p) {
        _delay(p + siz);
        return _get(p + siz);
    }
    void apply(int32_t lf, int32_t ri, F f) {
        lf += siz;
        ri += siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        while (lf < ri) {
            if (lf & 1) {
                tree[lf] = M::mapp(f, tree[lf]);
                del[lf] = M::comp(f, del[lf]);
                lf++;
            }
            if (ri & 1) {
                ri--;
                tree[ri] = M::mapp(f, tree[ri]);
                del[ri] = M::comp(f, del[ri]);
            }
            lf >>= 1;
            ri >>= 1;
        }
        _calc(dl);
        _calc(dr - 1);
    }
    T prod(int32_t lf, int32_t ri) {
        lf += siz;
        ri += siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        T rel = M::e;
        T rer = M::e;
        while (lf < ri) {
            if (lf & 1) {
                rel = M::op(rel, _get(lf));
                lf++;
            }
            if (ri & 1) {
                ri--;
                rer = M::op(_get(ri), rer);
            }
            lf >>= 1;
            ri >>= 1;
        }
        return M::op(rel, rer);
    }
    template <class F>
    int32_t max_right(int32_t lf, F f) {
        lf += siz;
        int32_t ri = siz << 1;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        std::queue<int32_t> lfp;
        std::stack<int32_t> rip;
        while (lf < ri) {
            if (lf & 1) {
                lfp.push(lf);
                lf++;
            }
            if (ri & 1) {
                ri--;
                rip.push(ri);
            }
            lf >>= 1;
            ri >>= 1;
        }
        T val = M::e;
        while (!lfp.empty()) {
            int32_t i = lfp.front();
            lfp.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    if (f(M::op(val, _get(i)))) {
                        val = M::op(val, _get(i));
                        i++;
                    }
                }
                return i - siz;
            }
            val = M::op(val, _get(i));
        }
        while (!rip.empty()) {
            int32_t i = rip.top();
            rip.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    if (f(M::op(val, _get(i)))) {
                        val = M::op(val, _get(i));
                        i++;
                    }
                }
                return i - siz;
            }
            val = M::op(val, _get(i));
        }
        return siz;
    }
    template <class F>
    int32_t min_left(int32_t ri, F f) {
        ri += siz;
        int32_t lf = siz;
        int32_t dl = lf >> (std::countr_zero((uint32_t)lf));
        int32_t dr = ri >> (std::countr_zero((uint32_t)ri));
        _delay(dl);
        _delay(dr - 1);
        std::queue<int32_t> rip;
        std::stack<int32_t> lfp;
        while (lf < ri) {
            if (lf & 1) {
                lfp.push(lf);
                lf++;
            }
            if (ri & 1) {
                ri--;
                rip.push(ri);
            }
            lf >>= 1;
            ri >>= 1;
        }
        T val = M::e;
        while (!rip.empty()) {
            int32_t i = rip.front();
            rip.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    i++;
                    if (f(M::op(_get(i), val))) {
                        val = M::op(_get(i), val);
                        i--;
                    }
                }
                return i - siz + 1;
            }
            val = M::op(_get(i), val);
        }
        while (!lfp.empty()) {
            int32_t i = lfp.top();
            lfp.pop();
            if (!f(M::op(val, _get(i)))) {
                while (i < siz) {
                    _del_segment(i);
                    i <<= 1;
                    i++;
                    if (f(M::op(_get(i), val))) {
                        val = M::op(_get(i), val);
                        i--;
                    }
                }
                return i - siz + 1;
            }
            val = M::op(_get(i), val);
        }
        return 0;
    }
    int32_t size() { return siz; }
};

Back to top page