shogo-library

競技プログラミング用の C++ ライブラリ

View the Project on GitHub shogo314/shogo-library

:heavy_check_mark: 2次元セグメント木
(src/data_structures/segtree-2d.hpp)

可換モノイド (algebra/monoid.hpp) を乗せる2次元セグメント木です。更新する座標と取得する範囲をすべて先読みして、必要なノードだけを持ちます。

std::vector<std::tuple<int, int>> sets = { {0, 1}, {2, 3} };        // set/apply する座標 (x, y)
std::vector<std::tuple<int, int, int, int>> prods = { {0, 3, 0, 4} }; // prod する範囲 (lx, rx, ly, ry)
RSumQ2D<long long> seg(3, 4, sets, prods);                         // x は [0, 3)、y は [0, 4)
seg.apply(0, 1, 5);
seg.apply(2, 3, 7);
seg.prod(0, 3, 0, 4);  // 12

座標が大きい場合は、先に座標圧縮してから使います。先読みしていない座標への set・apply や、先読みしていない範囲への prod の結果は保証されません。

別名

別名 実体 用途
RMaxQ2D<S> SegTree2D<monoid::Max<S>> 矩形の最大値
RMinQ2D<S> SegTree2D<monoid::Min<S>> 矩形の最小値
RSumQ2D<S> SegTree2D<monoid::Sum<S>> 矩形和

メンバ関数

$q$ を先読みしたクエリの数、$H$, $W$ を x, y 座標の範囲とします。

関数 説明 計算量
SegTree2D(h, w, set_query_indices, prod_query_indices, m = M()) x 座標 $[0, h)$、y 座標 $[0, w)$。すべて単位元で初期化 $O(q \log H \log W \log q)$
get(x, y) $(x, y)$ の値 $O(\log q)$
set(x, y, v) $(x, y)$ を v に更新 $O(\log H \log W \log q)$
apply(x, y, v) $(x, y)$ を op(get(x, y), v) に更新 $O(\log H \log W \log q)$
prod(lx, rx, ly, ry) $[l_x, r_x) \times [l_y, r_y)$ の積 $O(\log H \log W \log q)$

関連

Depends on

Verified with

Code

#pragma once

/**
 * @file segtree-2d.hpp
 * @brief 2次元セグメント木
 */

#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
#include "../algebra/monoid.hpp"

/**
 * @brief 2次元セグメント木 (更新・取得する座標を先読みして圧縮する)
 *
 * @tparam M 可換モノイド (algebra/monoid.hpp)
 */
template <typename M>
class SegTree2D {
public:
    using S = typename M::S;

private:
    M m;
    S op(const S& a, const S& b) const { return m.op(a, b); }
    S e() const { return m.e(); }

    int h, w, sz_x, sz_y, height_x, height_y;
    std::vector<std::vector<int>> y_indices;
    std::vector<std::vector<S>> data_compressed;

    S get_y(int kx, int ky) {
        ky += sz_y;
        auto it = std::lower_bound(y_indices[kx].begin(), y_indices[kx].end(), ky);
        if(it == y_indices[kx].end() || *it != ky) return e();
        return data_compressed[kx][it - y_indices[kx].begin()];
    }

    S updated_y(int kx, int ky, int child_y_idx, bool child_y_right, const S& child_val) {
        if(!child_y_right && child_y_idx+1 < (int)y_indices[kx].size() && y_indices[kx][child_y_idx+1] == ky*2+1) {
            return op(child_val, data_compressed[kx][child_y_idx+1]);
        }
        if(child_y_right && child_y_idx-1 >= 0 && y_indices[kx][child_y_idx-1] == ky*2) {
            return op(data_compressed[kx][child_y_idx-1], child_val);
        }
        return child_val;
    }

    void update_tree_y(int kx, int ky, const S& val) {
        ky += sz_y;
        int y_idx = std::lower_bound(y_indices[kx].begin(), y_indices[kx].end(), ky) - y_indices[kx].begin();
        S tmp_val = val;
        data_compressed[kx][y_idx] = tmp_val;
        for(int i = 1; i <= height_y; i++) {
            int child_y_idx = y_idx;
            y_idx = std::lower_bound(y_indices[kx].begin(), y_indices[kx].begin() + child_y_idx, ky >> i) - y_indices[kx].begin();
            tmp_val = data_compressed[kx][y_idx] = updated_y(kx, ky >> i, child_y_idx, ky>>(i-1)&1, tmp_val);
        }
    }

    S updated_x(int kx, int ky, bool child_x_right, const S& child_val) {
        if(!child_x_right) {
            return op(child_val, get_y(kx*2+1, ky));
        } else {
            return op(get_y(kx*2, ky), child_val);
        }
    }

    void update_tree_x(int kx, int ky, const S& val) {
        kx += sz_x;
        S tmp_val = val;
        update_tree_y(kx, ky, tmp_val);
        for(int i = 1; i <= height_x; i++) {
            tmp_val = updated_x(kx >> i, ky, kx>>(i-1)&1, tmp_val);
            update_tree_y(kx >> i, ky, tmp_val);
        }
    }

    S prod_y(int kx, int ly, int ry) {
        S left_prod = e(), right_prod = e();
        ly += sz_y; ry += sz_y;
        auto itr = y_indices[kx].end();
        while(ly < ry) {
            if(ry & 1) {
                --ry;
                itr = std::lower_bound(y_indices[kx].begin(), itr, ry);
                right_prod = op(data_compressed[kx][itr - y_indices[kx].begin()], right_prod);
            }
            if(ly & 1) {
                itr = std::lower_bound(y_indices[kx].begin(), itr, ly);
                left_prod = op(left_prod, data_compressed[kx][itr - y_indices[kx].begin()]);
                ++ly;
            }
            ly >>= 1; ry >>= 1;
        }
        return op(left_prod, right_prod);
    }

    S prod_x(int lx, int rx, int ly, int ry) {
        S left_prod = e(), right_prod = e();
        lx += sz_x; rx += sz_x;
        while(lx < rx) {
            if(lx & 1) {
                left_prod = op(left_prod, prod_y(lx++, ly, ry));
            }
            if(rx & 1) {
                right_prod = op(prod_y(--rx, ly, ry), right_prod);
            }
            lx >>= 1; rx >>= 1;
        }
        return op(left_prod, right_prod);
    }

    void construct_data(const std::vector<std::tuple<int, int>>& set_query_indices, const std::vector<std::tuple<int, int, int, int>>& prod_query_indices) {
        sz_x = 1; height_x = 0;
        while(sz_x < h) { sz_x <<= 1; ++height_x; }
        sz_y = 1; height_y = 0;
        while(sz_y < w) { sz_y <<= 1; ++height_y; }
        data_compressed.resize(sz_x*2);
        y_indices.resize(sz_x*2);

        for(auto [x, y] : set_query_indices) {
            x += sz_x;
            std::vector<int> x_indices_tmp;
            for(int i = 0; i <= height_x; ++i) {
                x_indices_tmp.push_back(x);
                x >>= 1;
            }
            y += sz_y;
            std::vector<int> y_indices_tmp;
            for(int i = 0; i <= height_y; ++i) {
                y_indices_tmp.push_back(y);
                y >>= 1;
            }
            for(int x : x_indices_tmp) {
                for(int y : y_indices_tmp) {
                    y_indices[x].push_back(y);
                }
            }
        }
        for(auto [lx, rx, ly, ry] : prod_query_indices) {
            std::vector<int> x_indices_tmp;
            lx += sz_x; rx += sz_x;
            while(lx < rx) {
                if(lx & 1) x_indices_tmp.push_back(lx++);
                if(rx & 1) x_indices_tmp.push_back(--rx);
                lx >>= 1; rx >>= 1;
            }
            ly += sz_y; ry += sz_y;
            std::vector<int> y_indices_tmp;
            while(ly < ry) {
                if(ly & 1) y_indices_tmp.push_back(ly++);
                if(ry & 1) y_indices_tmp.push_back(--ry);
                ly >>= 1; ry >>= 1;
            }
            for(int x : x_indices_tmp) {
                for(int y : y_indices_tmp) {
                    y_indices[x].push_back(y);
                }
            }
        }

        for(int x = 1; x < sz_x*2; x++) {
            std::sort(y_indices[x].begin(), y_indices[x].end());
            y_indices[x].erase(std::unique(y_indices[x].begin(), y_indices[x].end()), y_indices[x].end());
        }
        for(int i = 1; i < sz_x*2; ++i) {
            data_compressed[i].assign(y_indices[i].size(), e());
        }
    }

public:
    SegTree2D() = default;
    /**
     * @brief コンストラクタ
     *
     * @param h x座標の範囲 [0, h)
     * @param w y座標の範囲 [0, w)
     * @param set_query_indices set/apply する座標 (x, y) の列
     * @param prod_query_indices prod する範囲 (lx, rx, ly, ry) の列
     * @param m モノイド
     */
    explicit SegTree2D(int h, int w, const std::vector<std::tuple<int, int>>& set_query_indices, const std::vector<std::tuple<int, int, int, int>>& prod_query_indices, M m = M())
        : m(std::move(m)), h(h), w(w) {
        construct_data(set_query_indices, prod_query_indices);
    }

    /**
     * @brief 指定された要素の値を返す
     * @param kx x座標
     * @param ky y座標
     * @return 要素の値
     */
    S get(int kx, int ky) {
        kx += sz_x;
        return get_y(kx, ky);
    }

    /**
     * @brief 指定された要素の値をxに更新する
     * @param kx x座標
     * @param ky y座標
     * @param x 代入する値
     */
    void set(int kx, int ky, const S& x) {
        update_tree_x(kx, ky, x);
    }

    /**
     * @brief 指定された要素の値にxを作用させる
     *
     * @param kx x座標
     * @param ky y座標
     * @param x 作用素
     */
    void apply(int kx, int ky, const S& x) {
        set(kx, ky, op(get(kx, ky), x));
    }

    /**
     * @brief [lx, rx)x[ly, ry)の範囲の要素の総積を返す
     *
     * @param lx x座標の半開区間の開始
     * @param rx x座標の半開区間の終端
     * @param ly y座標の半開区間の開始
     * @param ry y座標の半開区間の終端
     */
    S prod(int lx, int rx, int ly, int ry) {
        return prod_x(lx, rx, ly, ry);
    }
};

template <typename M>
SegTree2D(int, int, std::vector<std::tuple<int, int>>, std::vector<std::tuple<int, int, int, int>>, M) -> SegTree2D<M>;

/**
 * @brief RangeMaxQuery
 *
 * @tparam S 型
 */
template <typename S>
using RMaxQ2D = SegTree2D<monoid::Max<S>>;
/**
 * @brief RangeMinQuery
 *
 * @tparam S 型
 */
template <typename S>
using RMinQ2D = SegTree2D<monoid::Min<S>>;
/**
 * @brief RangeSumQuery
 *
 * @tparam S 型
 */
template <typename S>
using RSumQ2D = SegTree2D<monoid::Sum<S>>;
#line 2 "src/data_structures/segtree-2d.hpp"

/**
 * @file segtree-2d.hpp
 * @brief 2次元セグメント木
 */

#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
#line 2 "src/algebra/monoid.hpp"

/**
 * @file monoid.hpp
 * @brief モノイドの定義
 *
 * モノイドは次のメンバを持つ型として表す
 * - using S: 要素の型
 * - S op(const S& a, const S& b): 積 (結合的)
 * - S e(): 単位元
 * op, e は static でも非 static でもよい (データ構造はモノイドのオブジェクトを保持して呼び出す)
 */

#line 15 "src/algebra/monoid.hpp"
#include <istream>
#include <limits>
#include <numeric>
#include <ostream>
#include <type_traits>
#line 21 "src/algebra/monoid.hpp"

/**
 * @brief 1次関数 f(x) = a * x + b
 *
 * monoid::Composite の要素や acted_monoid::AffineSum の作用素に使う
 * 例: Affine<mint> f{2, 3}; f(x) は 2x + 3。省略すると恒等写像 {1, 0}
 */
template <typename T>
struct Affine {
    T a = T(1);  //!< 傾き
    T b = T(0);  //!< 切片
    constexpr T operator()(const T& x) const { return a * x + b; }
    friend constexpr bool operator==(const Affine& f, const Affine& g) { return f.a == g.a && f.b == g.b; }
    friend constexpr bool operator!=(const Affine& f, const Affine& g) { return !(f == g); }
    template <class CharT, class Traits>
    friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, Affine& f) {
        return is >> f.a >> f.b;
    }
    template <class CharT, class Traits>
    friend std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const Affine& f) {
        return os << f.a << CharT(' ') << f.b;
    }
};

namespace monoid {

/**
 * @brief 和
 */
template <typename T>
struct Sum {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return a + b; }
    static constexpr S e() { return S(0); }
};

/**
 * @brief 積
 */
template <typename T>
struct Prod {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return a * b; }
    static constexpr S e() { return S(1); }
};

/**
 * @brief 最大値 単位元は型の最小値
 */
template <typename T>
struct Max {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return std::max(a, b); }
    static constexpr S e() { return std::numeric_limits<S>::lowest(); }
};

/**
 * @brief 最小値 単位元は型の最大値
 */
template <typename T>
struct Min {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return std::min(a, b); }
    static constexpr S e() { return std::numeric_limits<S>::max(); }
};

/**
 * @brief 最小値と最大値の組 {min, max}
 */
template <typename T>
struct MinMax {
    using S = std::pair<T, T>;
    static constexpr S op(const S& a, const S& b) { return {std::min(a.first, b.first), std::max(a.second, b.second)}; }
    static constexpr S e() { return {std::numeric_limits<T>::max(), std::numeric_limits<T>::lowest()}; }
};

/**
 * @brief 排他的論理和
 */
template <typename T>
struct Xor {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return a ^ b; }
    static constexpr S e() { return S(0); }
};

/**
 * @brief 論理積
 */
template <typename T>
struct And {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return a & b; }
    static constexpr S e() { return ~S(0); }
};

/**
 * @brief 論理和
 */
template <typename T>
struct Or {
    using S = T;
    static constexpr S op(const S& a, const S& b) { return a | b; }
    static constexpr S e() { return S(0); }
};

/**
 * @brief 最大公約数 単位元は0
 */
template <typename T>
struct Gcd {
    static_assert(std::is_integral_v<T>);
    using S = T;
    static constexpr S op(const S& a, const S& b) { return std::gcd(a, b); }
    static constexpr S e() { return S(0); }
};

/**
 * @brief 最小公倍数 単位元は1
 */
template <typename T>
struct Lcm {
    static_assert(std::is_integral_v<T>);
    using S = T;
    static constexpr S op(const S& a, const S& b) { return std::lcm(a, b); }
    static constexpr S e() { return S(1); }
};

/**
 * @brief 1次関数 (Affine) の合成
 * op(f, g) = g∘f (左から順に適用する)
 * 区間 [l, r) の積は f_{r-1}(...f_l(x)) を表す
 */
template <typename T>
struct Composite {
    using S = Affine<T>;
    static constexpr S op(const S& f, const S& g) { return {g.a * f.a, g.a * f.b + g.b}; }
    static constexpr S e() { return {T(1), T(0)}; }
};

/**
 * @brief 括弧列 対応の取れていない ')' と '(' の個数
 */
struct Parenthesis {
    struct S {
        long long close; // 対応の取れていない ')' の個数
        long long open;  // 対応の取れていない '(' の個数
        constexpr S(char c = 0) : close(c == ')'), open(c == '(') {}
        constexpr S(long long close, long long open) : close(close), open(open) {}
        /**
         * @brief 正しい括弧列か
         */
        constexpr bool is_valid() const { return close == 0 && open == 0; }
    };
    static constexpr S op(const S& a, const S& b) {
        if(a.open >= b.close) return S(a.close, a.open - b.close + b.open);
        return S(a.close + b.close - a.open, b.open);
    }
    static constexpr S e() { return S(); }
};

/**
 * @brief 最小値とその位置 同じ値なら左側を優先
 *
 * @tparam T 値の型
 * @tparam U 位置などの付随する値の型
 */
template <typename T, typename U = int>
struct MinWith {
    using S = std::pair<T, U>;
    static constexpr S op(const S& a, const S& b) { return b.first < a.first ? b : a; }
    static constexpr S e() { return {std::numeric_limits<T>::max(), U{}}; }
};

/**
 * @brief 最大値とその位置 同じ値なら左側を優先
 *
 * @tparam T 値の型
 * @tparam U 位置などの付随する値の型
 */
template <typename T, typename U = int>
struct MaxWith {
    using S = std::pair<T, U>;
    static constexpr S op(const S& a, const S& b) { return a.first < b.first ? b : a; }
    static constexpr S e() { return {std::numeric_limits<T>::lowest(), U{}}; }
};

/**
 * @brief 最小値とその個数
 *
 * @tparam T 値の型
 * @tparam U 個数の型
 */
template <typename T, typename U = long long>
struct MinCount {
    using S = std::pair<T, U>;
    static constexpr S op(const S& a, const S& b) {
        if(a.first < b.first) return a;
        if(b.first < a.first) return b;
        return {a.first, a.second + b.second};
    }
    static constexpr S e() { return {std::numeric_limits<T>::max(), U(0)}; }
};

/**
 * @brief 最大値とその個数
 *
 * @tparam T 値の型
 * @tparam U 個数の型
 */
template <typename T, typename U = long long>
struct MaxCount {
    using S = std::pair<T, U>;
    static constexpr S op(const S& a, const S& b) {
        if(a.first < b.first) return b;
        if(b.first < a.first) return a;
        return {a.first, a.second + b.second};
    }
    static constexpr S e() { return {std::numeric_limits<T>::lowest(), U(0)}; }
};

} // namespace monoid

/**
 * @brief 関数オブジェクトと単位元から実行時に作るモノイド
 * ラムダ式を使える
 *
 * 例: SegTree seg(v, Monoid([](int a, int b) { return std::max(a, b); }, -1));
 *
 * @tparam T 要素の型
 * @tparam Op 積の関数オブジェクトの型
 */
template <typename T, typename Op>
struct Monoid {
    using S = T;
    Op op_object;
    S identity;
    Monoid() = default;
    constexpr Monoid(Op op, const S& e) : op_object(std::move(op)), identity(e) {}
    constexpr S op(const S& a, const S& b) const { return op_object(a, b); }
    constexpr S e() const { return identity; }
};
template <typename Op, typename T>
Monoid(Op, T) -> Monoid<T, Op>;
#line 13 "src/data_structures/segtree-2d.hpp"

/**
 * @brief 2次元セグメント木 (更新・取得する座標を先読みして圧縮する)
 *
 * @tparam M 可換モノイド (algebra/monoid.hpp)
 */
template <typename M>
class SegTree2D {
public:
    using S = typename M::S;

private:
    M m;
    S op(const S& a, const S& b) const { return m.op(a, b); }
    S e() const { return m.e(); }

    int h, w, sz_x, sz_y, height_x, height_y;
    std::vector<std::vector<int>> y_indices;
    std::vector<std::vector<S>> data_compressed;

    S get_y(int kx, int ky) {
        ky += sz_y;
        auto it = std::lower_bound(y_indices[kx].begin(), y_indices[kx].end(), ky);
        if(it == y_indices[kx].end() || *it != ky) return e();
        return data_compressed[kx][it - y_indices[kx].begin()];
    }

    S updated_y(int kx, int ky, int child_y_idx, bool child_y_right, const S& child_val) {
        if(!child_y_right && child_y_idx+1 < (int)y_indices[kx].size() && y_indices[kx][child_y_idx+1] == ky*2+1) {
            return op(child_val, data_compressed[kx][child_y_idx+1]);
        }
        if(child_y_right && child_y_idx-1 >= 0 && y_indices[kx][child_y_idx-1] == ky*2) {
            return op(data_compressed[kx][child_y_idx-1], child_val);
        }
        return child_val;
    }

    void update_tree_y(int kx, int ky, const S& val) {
        ky += sz_y;
        int y_idx = std::lower_bound(y_indices[kx].begin(), y_indices[kx].end(), ky) - y_indices[kx].begin();
        S tmp_val = val;
        data_compressed[kx][y_idx] = tmp_val;
        for(int i = 1; i <= height_y; i++) {
            int child_y_idx = y_idx;
            y_idx = std::lower_bound(y_indices[kx].begin(), y_indices[kx].begin() + child_y_idx, ky >> i) - y_indices[kx].begin();
            tmp_val = data_compressed[kx][y_idx] = updated_y(kx, ky >> i, child_y_idx, ky>>(i-1)&1, tmp_val);
        }
    }

    S updated_x(int kx, int ky, bool child_x_right, const S& child_val) {
        if(!child_x_right) {
            return op(child_val, get_y(kx*2+1, ky));
        } else {
            return op(get_y(kx*2, ky), child_val);
        }
    }

    void update_tree_x(int kx, int ky, const S& val) {
        kx += sz_x;
        S tmp_val = val;
        update_tree_y(kx, ky, tmp_val);
        for(int i = 1; i <= height_x; i++) {
            tmp_val = updated_x(kx >> i, ky, kx>>(i-1)&1, tmp_val);
            update_tree_y(kx >> i, ky, tmp_val);
        }
    }

    S prod_y(int kx, int ly, int ry) {
        S left_prod = e(), right_prod = e();
        ly += sz_y; ry += sz_y;
        auto itr = y_indices[kx].end();
        while(ly < ry) {
            if(ry & 1) {
                --ry;
                itr = std::lower_bound(y_indices[kx].begin(), itr, ry);
                right_prod = op(data_compressed[kx][itr - y_indices[kx].begin()], right_prod);
            }
            if(ly & 1) {
                itr = std::lower_bound(y_indices[kx].begin(), itr, ly);
                left_prod = op(left_prod, data_compressed[kx][itr - y_indices[kx].begin()]);
                ++ly;
            }
            ly >>= 1; ry >>= 1;
        }
        return op(left_prod, right_prod);
    }

    S prod_x(int lx, int rx, int ly, int ry) {
        S left_prod = e(), right_prod = e();
        lx += sz_x; rx += sz_x;
        while(lx < rx) {
            if(lx & 1) {
                left_prod = op(left_prod, prod_y(lx++, ly, ry));
            }
            if(rx & 1) {
                right_prod = op(prod_y(--rx, ly, ry), right_prod);
            }
            lx >>= 1; rx >>= 1;
        }
        return op(left_prod, right_prod);
    }

    void construct_data(const std::vector<std::tuple<int, int>>& set_query_indices, const std::vector<std::tuple<int, int, int, int>>& prod_query_indices) {
        sz_x = 1; height_x = 0;
        while(sz_x < h) { sz_x <<= 1; ++height_x; }
        sz_y = 1; height_y = 0;
        while(sz_y < w) { sz_y <<= 1; ++height_y; }
        data_compressed.resize(sz_x*2);
        y_indices.resize(sz_x*2);

        for(auto [x, y] : set_query_indices) {
            x += sz_x;
            std::vector<int> x_indices_tmp;
            for(int i = 0; i <= height_x; ++i) {
                x_indices_tmp.push_back(x);
                x >>= 1;
            }
            y += sz_y;
            std::vector<int> y_indices_tmp;
            for(int i = 0; i <= height_y; ++i) {
                y_indices_tmp.push_back(y);
                y >>= 1;
            }
            for(int x : x_indices_tmp) {
                for(int y : y_indices_tmp) {
                    y_indices[x].push_back(y);
                }
            }
        }
        for(auto [lx, rx, ly, ry] : prod_query_indices) {
            std::vector<int> x_indices_tmp;
            lx += sz_x; rx += sz_x;
            while(lx < rx) {
                if(lx & 1) x_indices_tmp.push_back(lx++);
                if(rx & 1) x_indices_tmp.push_back(--rx);
                lx >>= 1; rx >>= 1;
            }
            ly += sz_y; ry += sz_y;
            std::vector<int> y_indices_tmp;
            while(ly < ry) {
                if(ly & 1) y_indices_tmp.push_back(ly++);
                if(ry & 1) y_indices_tmp.push_back(--ry);
                ly >>= 1; ry >>= 1;
            }
            for(int x : x_indices_tmp) {
                for(int y : y_indices_tmp) {
                    y_indices[x].push_back(y);
                }
            }
        }

        for(int x = 1; x < sz_x*2; x++) {
            std::sort(y_indices[x].begin(), y_indices[x].end());
            y_indices[x].erase(std::unique(y_indices[x].begin(), y_indices[x].end()), y_indices[x].end());
        }
        for(int i = 1; i < sz_x*2; ++i) {
            data_compressed[i].assign(y_indices[i].size(), e());
        }
    }

public:
    SegTree2D() = default;
    /**
     * @brief コンストラクタ
     *
     * @param h x座標の範囲 [0, h)
     * @param w y座標の範囲 [0, w)
     * @param set_query_indices set/apply する座標 (x, y) の列
     * @param prod_query_indices prod する範囲 (lx, rx, ly, ry) の列
     * @param m モノイド
     */
    explicit SegTree2D(int h, int w, const std::vector<std::tuple<int, int>>& set_query_indices, const std::vector<std::tuple<int, int, int, int>>& prod_query_indices, M m = M())
        : m(std::move(m)), h(h), w(w) {
        construct_data(set_query_indices, prod_query_indices);
    }

    /**
     * @brief 指定された要素の値を返す
     * @param kx x座標
     * @param ky y座標
     * @return 要素の値
     */
    S get(int kx, int ky) {
        kx += sz_x;
        return get_y(kx, ky);
    }

    /**
     * @brief 指定された要素の値をxに更新する
     * @param kx x座標
     * @param ky y座標
     * @param x 代入する値
     */
    void set(int kx, int ky, const S& x) {
        update_tree_x(kx, ky, x);
    }

    /**
     * @brief 指定された要素の値にxを作用させる
     *
     * @param kx x座標
     * @param ky y座標
     * @param x 作用素
     */
    void apply(int kx, int ky, const S& x) {
        set(kx, ky, op(get(kx, ky), x));
    }

    /**
     * @brief [lx, rx)x[ly, ry)の範囲の要素の総積を返す
     *
     * @param lx x座標の半開区間の開始
     * @param rx x座標の半開区間の終端
     * @param ly y座標の半開区間の開始
     * @param ry y座標の半開区間の終端
     */
    S prod(int lx, int rx, int ly, int ry) {
        return prod_x(lx, rx, ly, ry);
    }
};

template <typename M>
SegTree2D(int, int, std::vector<std::tuple<int, int>>, std::vector<std::tuple<int, int, int, int>>, M) -> SegTree2D<M>;

/**
 * @brief RangeMaxQuery
 *
 * @tparam S 型
 */
template <typename S>
using RMaxQ2D = SegTree2D<monoid::Max<S>>;
/**
 * @brief RangeMinQuery
 *
 * @tparam S 型
 */
template <typename S>
using RMinQ2D = SegTree2D<monoid::Min<S>>;
/**
 * @brief RangeSumQuery
 *
 * @tparam S 型
 */
template <typename S>
using RSumQ2D = SegTree2D<monoid::Sum<S>>;
Back to top page