library

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

View the Project on GitHub maspypy/library

:heavy_check_mark: ds/wavelet_matrix/wavelet_matrix_2d_range.hpp

Depends on

Verified with

Code

#include "ds/wavelet_matrix/wavelet_matrix.hpp"
#include "ds/index_compression.hpp"

template <typename XY, bool compress_X, bool compress_Y,
          typename SEGTREE = Dummy_Data_Structure>
struct Wavelet_Matrix_2D_Range {
  // 点群を X 昇順に並べる.
  Wavelet_Matrix<XY, compress_Y, SEGTREE> WM;
  using Mono = typename SEGTREE::MX;
  using T = typename Mono::value_type;
  static_assert(Mono::commute);

  Index_Compression<XY, false, !compress_X> IDX_X;

  int n;
  vc<int> new_idx;

  template <typename F>
  Wavelet_Matrix_2D_Range(int n, F f) {
    build(n, f);
  }

  template <typename F>
  void build(int m, F f) {
    n = m;
    vc<XY> X(n), Y(n);
    vc<T> S(n);
    FOR(i, n) {
      auto tmp = f(i);
      X[i] = get<0>(tmp), Y[i] = get<1>(tmp), S[i] = get<2>(tmp);
    }
    new_idx = IDX_X.build(X);
    vc<int> I(n);
    FOR(i, n) I[new_idx[i]] = i;
    Y = rearrange(Y, I);
    S = rearrange(S, I);
    WM.build(n, [&](int i) -> pair<XY, T> { return {Y[i], S[i]}; });
  }

  int count(XY x1, XY x2, XY y1, XY y2) {
    return WM.count(IDX_X(x1), IDX_X(x2), y1, y2);
  }

  // [L,R) x [-inf,y)
  pair<int, T> prefix_count_and_prod(XY x1, XY x2, XY y) {
    return WM.prefix_count_and_prod(IDX_X(x1), IDX_X(x2), y);
  }

  // [L,R) x [y1,y2)
  pair<int, T> count_and_prod(XY x1, XY x2, XY y1, XY y2) {
    return WM.count_and_prod(IDX_X(x1), IDX_X(x2), y1, y2);
  }

  // [L,R) x [-inf,inf)
  T prod_all(XY x1, XY x2) { return WM.prod_all(IDX_X(x1), IDX_X(x2)); }
  // [L,R) x [-inf,y)
  T prefix_prod(XY x1, XY x2, XY y) {
    return WM.prefix_prod(IDX_X(x1), IDX_X(x2), y);
  }
  // [L,R) x [y1,y2)
  T prod(XY x1, XY x2, XY y1, XY y2) {
    return WM.prod(IDX_X(x1), IDX_X(x2), y1, y2);
  }
  // i は最初に渡したインデックス
  void set(int i, T t) { WM.set(new_idx[i], t); }
  // i は最初に渡したインデックス
  void multiply(int i, T t) { WM.multiply(new_idx[i], t); }
  void add(int i, T t) { WM.multiply(new_idx[i], t); }
};
#line 1 "ds/bit_vector.hpp"
struct Bit_Vector {
  int n;
  bool prepared = 0;
  vc<pair<u64, u32>> dat;
  Bit_Vector(int n = 0) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
  void set(int i) {
    assert(!prepared && (0 <= i && i < n));
    dat[i >> 6].fi |= u64(1) << (i & 63);
  }
  void reset() {
    fill(all(dat), pair<u64, u32>{0, 0});
    prepared = 0;
  }
  void build() {
    prepared = 1;
    FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
  }
  bool operator[](int i) const { return dat[i >> 6].fi >> (i & 63) & 1; }
  // [0, k) 内の 1 の個数
  int count_prefix(int k, bool f = true) const {
    assert(prepared);
    auto [a, b] = dat[k >> 6];
    int ret = b + popcnt(a & ((u64(1) << (k & 63)) - 1));
    return (f ? ret : k - ret);
  }
  int count(int L, int R, bool f = true) const {
    return count_prefix(R, f) - count_prefix(L, f);
  }
  string to_string() const {
    string ans;
    FOR(i, n) ans += '0' + (dat[i / 64].fi >> (i % 64) & 1);
    return ans;
  }
};
#line 1 "alg/monoid/dummy.hpp"
struct Monoid_Dummy {
  using value_type = char;
  static constexpr bool commute = true;
  static value_type op(value_type, value_type) { return 0; }
  static value_type unit() { return 0; }
};
#line 2 "ds/dummy_data_structure.hpp"

struct Dummy_Data_Structure {
  using MX = Monoid_Dummy;
  using T = typename MX::value_type;
  void build(const vc<T>& A) {}
};
#line 3 "ds/wavelet_matrix/wavelet_matrix.hpp"

template <typename Y, typename SEGTREE>
struct Uncompressed_Wavelet_Matrix {
  using Mono = typename SEGTREE::MX;
  using T = typename Mono::value_type;
  static_assert(Mono::commute);
  static_assert(is_same_v<Y, int> || is_same_v<Y, ll>);
  int n = 0, log = 0;
  vc<int> mid;
  vc<Bit_Vector> bv;
  vc<SEGTREE> seg;
  Y limit;

  Uncompressed_Wavelet_Matrix() = default;

  // f(i) = {A[i], dat[i]}

  template <typename F>
  Uncompressed_Wavelet_Matrix(int n, F f, int log = -1) {
    build(n, f, log);
  }
  Uncompressed_Wavelet_Matrix(const vc<Y>& A, int log = -1) {
    static_assert(is_same_v<SEGTREE, Dummy_Data_Structure>);
    build(
        len(A), [&](int i) -> pair<Y, T> { return {A[i], Mono::unit()}; }, log);
  }

  template <typename F>
  void build(int n, F f, int log = -1) {
    this->n = n;
    vc<Y> A(n);
    vc<T> S(n);
    FOR(i, n) tie(A[i], S[i]) = f(i);
    if (log == -1) {
      log = (n == 0 ? 0 : topbit(MAX(A)) + 1);
    } else {
      for (auto& x : A) assert(0 <= x && topbit(x) < log);
    }
    this->log = log;
    limit = Y(1) << log;
    if constexpr (is_same_v<Y, int>) assert(0 <= log && log <= 30);
    if constexpr (is_same_v<Y, ll>) assert(0 <= log && log <= 62);
    mid.resize(log), bv.assign(log, Bit_Vector(n));
    vc<Y> A0(n), A1(n);
    vc<T> S0(n), S1(n);
    seg.resize(log + 1);
    seg[log].build(S);
    for (int d = log - 1; d >= 0; --d) {
      int p0 = 0, p1 = 0;
      for (int i = 0; i < n; ++i) {
        if (A[i] >> d & 1) {
          bv[d].set(i), A1[p1] = A[i], S1[p1] = S[i], p1++;
        } else {
          A0[p0] = A[i], S0[p0] = S[i], p0++;
        }
      }
      swap(A, A0), swap(S, S0);
      move(A1.begin(), A1.begin() + p1, A.begin() + p0);
      move(S1.begin(), S1.begin() + p1, S.begin() + p0);
      mid[d] = p0, bv[d].build(), seg[d].build(S);
    }
  }

  tuple<int, int, int, int> get_subtree(int d, int L, int R) const {
    assert(1 <= d && d <= log);
    int a = bv[d - 1].count_prefix(L), b = bv[d - 1].count_prefix(R);
    return {L - a, R - b, mid[d - 1] + a, mid[d - 1] + b};
  }

  template <typename F>
  void work_point(F f, int i) {
    assert(0 <= i && i < n);
    f(log, i);
    FOR_R(d, log) {
      int a = bv[d].count_prefix(i);
      if (bv[d][i]) {
        i = mid[d] + a;
      } else {
        i = i - a;
      }
      f(d, i);
    }
  }

  template <typename F>
  void work_prefix(F f, int L, int R, Y y) const {
    chmin(y, limit);
    if (y == 0) return;
    if (y == limit) {
      f(log, L, R);
      return;
    }
    FOR_R(d, log) {
      auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
      if (y >> d & 1) {
        f(d, L0, R0);
        L = L1, R = R1;
      } else {
        L = L0, R = R0;
      }
    }
  }

  template <typename F>
  void work_range(F f, int L, int R, Y y1, Y y2) const {
    chmin(y2, limit);
    if (y1 >= y2) return;
    assert(0 <= y1 && y1 <= y2 && y2 <= limit);
    if (y1 == 0) return work_prefix(f, L, R, y2);
    auto dfs = [&](auto& dfs, int d, int L, int R, Y y1, Y y2) -> void {
      if (y1 == y2) return;
      if (y1 == 0 && y2 == Y(1) << d) {
        f(d, L, R);
        return;
      }
      assert(d > 0);
      auto [L0, R0, L1, R1] = get_subtree(d, L, R);
      Y m = (Y(1) << (d - 1));

      if (y2 <= m) {
        dfs(dfs, d - 1, L0, R0, y1, y2);
      } else if (y1 >= m) {
        dfs(dfs, d - 1, L1, R1, y1 - m, y2 - m);
      } else {
        dfs(dfs, d - 1, L0, R0, y1, m);
        dfs(dfs, d - 1, L1, R1, 0, y2 - m);
      }
    };
    dfs(dfs, log, L, R, y1, y2);
  }

  // [L,R) x [0,y)

  int prefix_count(int L, int R, Y y) const {
    int cnt = 0;
    work_prefix([&](int d, int a, int b) { cnt += b - a; }, L, R, y);
    return cnt;
  }

  // [L,R) x [y1,y2)

  int count(int L, int R, Y y1, Y y2) const {
    return prefix_count(L, R, y2) - prefix_count(L, R, y1);
  }

  // [L,R) x [0,y)

  T prefix_prod(int L, int R, Y y) const {
    T ans = Mono::unit();
    work_prefix(
        [&](int d, int a, int b) { ans = Mono::op(ans, seg[d].prod(a, b)); }, L,
        R, y);
    return ans;
  }
  // [L,R) x [y1,y2)

  T prod(int L, int R, Y y1, Y y2) const {
    T ans = Mono::unit();
    work_range(
        [&](int d, int a, int b) { ans = Mono::op(ans, seg[d].prod(a, b)); }, L,
        R, y1, y2);
    return ans;
  }
  T prod_all(int L, int R) const { return seg[log].prod(L, R); }

  // [L,R) x [0,y)

  pair<int, T> prefix_count_and_prod(int L, int R, Y y) const {
    pair<int, T> ans = {0, Mono::unit()};
    work_prefix(
        [&](int d, int a, int b) {
          ans.fi += b - a;
          ans.se = Mono::op(ans.se, seg[d].prod(a, b));
        },
        L, R, y);
    return ans;
  }
  // [L,R) x [y1,y2)

  pair<int, T> count_and_prod(int L, int R, Y y1, Y y2) const {
    pair<int, T> ans = {0, Mono::unit()};
    work_range(
        [&](int d, int a, int b) {
          ans.fi += b - a;
          ans.se = Mono::op(ans.se, seg[d].prod(a, b));
        },
        L, R, y1, y2);
    return ans;
  }

  Y kth(int L, int R, int k) const {
    assert(0 <= k && k < R - L);
    Y ans = 0;
    for (int d = log - 1; d >= 0; --d) {
      auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
      if (k < R0 - L0) {
        L = L0, R = R0;
      } else {
        ans |= Y(1) << d;
        k -= R0 - L0, L = L1, R = R1;
      }
    }
    return ans;
  }

  template <bool upper>
  Y median(int L, int R) const {
    assert(0 <= L && L < R && R <= n);
    int k = (upper ? (R - L) / 2 : (R - L - 1) / 2);
    return kth(L, R, k);
  }

  void set(int i, T t) {
    assert(0 <= i && i < n);
    work_point([&](int d, int i) { seg[d].set(i, t); }, i);
  }
  void multiply(int i, T t) {
    assert(0 <= i && i < n);
    work_point([&](int d, int i) { seg[d].multiply(i, t); }, i);
  }
  void add(int i, T t) {
    assert(0 <= i && i < n);
    work_point([&](int d, int i) { seg[d].add(i, t); }, i);
  }

  // [L,R) x [0,y) での check(y, cnt, prod) が true となる最大の (Y,cnt,prod)

  template <typename F>
  tuple<Y, int, T> max_right(F check, int L, int R) const {
    assert(limit < infty<Y>);
    int cnt = 0;
    Y y = 0;
    T t = Mono::unit();
    T t_all = seg[log].prod(L, R);
    assert(check(0, 0, Mono::unit()));
    if (check(limit, R - L, t_all)) {
      y = binary_search([&](Y y) -> bool { return check(y, R - L, t_all); },
                        limit, infty<Y> + 1);
      return {y, R - L, t_all};
    }
    for (int d = log - 1; d >= 0; --d) {
      auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
      Y y1 = y | Y(1) << d;
      int cnt1 = cnt + R0 - L0;
      T t1 = Mono::op(t, seg[d].prod(L0, R0));
      if (check(y1, cnt1, t1)) {
        y = y1, cnt = cnt1, t = t1, L = L1, R = R1;
      } else {
        L = L0, R = R0;
      }
    }
    return {y, cnt, t};
  }

  // [L,R) x [0,y) での check(y, cnt, prod) が true となる最大の (Y,cnt,prod)

  template <typename F>
  tuple<Y, int, T> max_right_many(F check, vc<pair<int, int>> LR) const {
    assert(limit < infty<Y>);
    int cnt = 0;
    Y y = 0;
    T t = Mono::unit();
    T t_all = Mono::unit();
    int cnt_all = 0;
    for (auto& [l, r] : LR)
      t_all = Mono::op(t_all, prod_all(l, r)), cnt_all += r - l;
    assert(check(0, 0, Mono::unit()));
    if (check(limit, cnt_all, t_all)) {
      y = binary_search([&](Y y) -> bool { return check(y, cnt_all, t_all); },
                        limit, infty<Y> + 1);
      return {y, cnt_all, t_all};
    }
    for (int d = log - 1; d >= 0; --d) {
      Y y1 = Y(1) << d;
      T t1 = t;
      int cnt1 = 0;
      for (auto& [L, R] : LR) {
        auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
        cnt1 += R0 - L0;
        t1 = Mono::op(t1, seg[d].prod(L0, R0));
      }
      if (check(y1, cnt1, t1)) {
        y = y1, cnt = cnt1, t = t1;
        for (auto& [L, R] : LR) {
          auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
          L = L1, R = R1;
        }
      } else {
        for (auto& [L, R] : LR) {
          auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
          L = L0, R = R0;
        }
      }
    }
    return {y, cnt, t};
  }

  // [L,R) x [y, inf) での check(y, cnt, prod) が true となる最小の (y,cnt,prod)

  // cnt==0 だと true であることは仮定する

  // https://qoj.ac/contest/1047/problem/5094

  template <typename F>
  tuple<Y, int, T> min_left_many(F check, vc<pair<int, int>> LR) const {
    assert(check(limit, 0, Mono::unit()));
    int cnt = 0;
    Y y = limit;
    T t = Mono::unit();
    T t_all = Mono::unit();
    int cnt_all = 0;
    for (auto& [l, r] : LR)
      t_all = Mono::op(t_all, prod_all(l, r)), cnt_all += r - l;
    if (check(0, cnt_all, t_all)) {
      return {0, cnt_all, t_all};
    }
    for (int d = log - 1; d >= 0; --d) {
      Y y1 = y - (Y(1) << d);
      T t1 = t;
      int cnt1 = cnt;
      for (auto& [L, R] : LR) {
        auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
        cnt1 += R1 - L1;
        t1 = Mono::op(t1, seg[d].prod(L1, R1));
      }
      if (check(y1, cnt1, t1)) {
        y = y1, cnt = cnt1, t = t1;
        SHOW(y);
        for (auto& [L, R] : LR) {
          auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
          L = L0, R = R0;
        }
      } else {
        for (auto& [L, R] : LR) {
          auto [L0, R0, L1, R1] = get_subtree(d + 1, L, R);
          L = L1, R = R1;
        }
      }
    }
    SHOW(y, cnt, t);
    return {y, cnt, t};
  }
};

template <typename Y, typename SEGTREE>
struct Compressed_Wavelet_Matrix {
  using Mono = typename SEGTREE::MX;
  using T = typename Mono::value_type;

  int n = 0;
  vc<Y> key;
  Uncompressed_Wavelet_Matrix<int, SEGTREE> wm;

  Compressed_Wavelet_Matrix() = default;

  // f(i) = {A[i], dat[i]}

  template <typename F>
  Compressed_Wavelet_Matrix(int n, F f) {
    build(n, f);
  }

  Compressed_Wavelet_Matrix(const vc<Y>& A) {
    static_assert(is_same_v<SEGTREE, Dummy_Data_Structure>);
    build(A);
  }

  template <typename F>
  void build(int n, F f) {
    this->n = n;
    vc<Y> A(n);
    vc<T> S(n);
    FOR(i, n) tie(A[i], S[i]) = f(i);

    key = A;
    UNIQUE(key);

    wm.build(n, [&](int i) -> pair<int, T> {
      int k = LB(key, A[i]);
      return {k, S[i]};
    });
  }

  void build(const vc<Y>& A) {
    static_assert(is_same_v<SEGTREE, Dummy_Data_Structure>);
    n = len(A);
    key = A;
    UNIQUE(key);

    wm.build(n, [&](int i) -> pair<int, T> {
      int k = LB(key, A[i]);
      return {k, Mono::unit()};
    });
  }

  Y kth(int L, int R, int k) const { return key[wm.kth(L, R, k)]; }

  template <bool upper>
  Y median(int L, int R) const {
    return key[wm.template median<upper>(L, R)];
  }

  // [L,R) x [-inf,y)

  int prefix_count(int L, int R, Y y) const {
    return wm.prefix_count(L, R, LB(key, y));
  }

  // [L,R) x [y1,y2)

  int count(int L, int R, Y y1, Y y2) const {
    return wm.count(L, R, LB(key, y1), LB(key, y2));
  }

  // [L,R) x [-inf,y)

  T prefix_prod(int L, int R, Y y) const {
    return wm.prefix_prod(L, R, LB(key, y));
  }

  // [L,R) x [y1,y2)

  T prod(int L, int R, Y y1, Y y2) const {
    return wm.prod(L, R, LB(key, y1), LB(key, y2));
  }

  T prod_all(int L, int R) const { return wm.prod_all(L, R); }

  // [L,R) x [-inf,y)

  pair<int, T> prefix_count_and_prod(int L, int R, Y y) const {
    return wm.prefix_count_and_prod(L, R, LB(key, y));
  }

  // [L,R) x [y1,y2)

  pair<int, T> count_and_prod(int L, int R, Y y1, Y y2) const {
    return wm.count_and_prod(L, R, LB(key, y1), LB(key, y2));
  }

  void set(int i, T t) { wm.set(i, t); }

  void multiply(int i, T t) { wm.multiply(i, t); }

  void add(int i, T t) { wm.add(i, t); }
};

template <typename Y, bool compress, typename SEGTREE = Dummy_Data_Structure>
using Wavelet_Matrix =
    conditional_t<compress, Compressed_Wavelet_Matrix<Y, SEGTREE>,
                  Uncompressed_Wavelet_Matrix<Y, SEGTREE>>;
#line 1 "ds/index_compression.hpp"
template <typename T>
struct Index_Compression_DISTINCT_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<int> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1]++;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi]++;
    }
    FOR_R(i, 1, len(dat)) dat[i] = dat[i - 1];
    dat[0] = 0;
    return X;
  }
  int size() { return len(dat); }
  int operator()(ll x) { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
};

template <typename T>
struct Index_Compression_SAME_SMALL {
  int mi, ma;
  vc<T> dat;
  vc<T> build(vc<T> X) {
    mi = 0, ma = -1;
    if (!X.empty()) mi = MIN(X), ma = MAX(X);
    dat.assign(ma - mi + 2, 0);
    for (auto& x : X) dat[x - mi + 1] = 1;
    FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
    for (auto& x : X) {
      x = dat[x - mi];
    }
    return X;
  }
  int size() { return len(dat); }
  int operator()(ll x) { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
};

template <typename T>
struct Index_Compression_SAME_LARGE {
  vc<T> dat;
  vc<int> build(vc<T> X) {
    vc<int> I = argsort(X);
    vc<int> res(len(X));
    for (auto& i : I) {
      if (!dat.empty() && dat.back() == X[i]) {
        res[i] = len(dat) - 1;
      } else {
        res[i] = len(dat);
        dat.eb(X[i]);
      }
    }
    dat.shrink_to_fit();
    return res;
  }
  int size() { return len(dat); }
  int operator()(T x) { return LB(dat, x); }
};

template <typename T>
struct Index_Compression_DISTINCT_LARGE {
  vc<T> dat;
  vc<int> build(vc<T> X) {
    vc<int> I = argsort(X);
    vc<int> res(len(X));
    for (auto& i : I) {
      res[i] = len(dat), dat.eb(X[i]);
    }
    dat.shrink_to_fit();
    return res;
  }
  int size() { return len(dat); }
  int operator()(T x) { return LB(dat, x); }
};

template <typename T, bool SMALL>
using Index_Compression_DISTINCT =
    typename std::conditional<SMALL, Index_Compression_DISTINCT_SMALL<T>,
                              Index_Compression_DISTINCT_LARGE<T>>::type;
template <typename T, bool SMALL>
using Index_Compression_SAME =
    typename std::conditional<SMALL, Index_Compression_SAME_SMALL<T>,
                              Index_Compression_SAME_LARGE<T>>::type;

// SAME: [2,3,2] -> [0,1,0]
// DISTINCT: [2,2,3] -> [0,2,1]
// build で列を圧縮してくれる. そのあと
// (x): lower_bound(X,x) をかえす
template <typename T, bool SAME, bool SMALL>
using Index_Compression =
    typename std::conditional<SAME, Index_Compression_SAME<T, SMALL>,
                              Index_Compression_DISTINCT<T, SMALL>>::type;
#line 3 "ds/wavelet_matrix/wavelet_matrix_2d_range.hpp"

template <typename XY, bool compress_X, bool compress_Y,
          typename SEGTREE = Dummy_Data_Structure>
struct Wavelet_Matrix_2D_Range {
  // 点群を X 昇順に並べる.
  Wavelet_Matrix<XY, compress_Y, SEGTREE> WM;
  using Mono = typename SEGTREE::MX;
  using T = typename Mono::value_type;
  static_assert(Mono::commute);

  Index_Compression<XY, false, !compress_X> IDX_X;

  int n;
  vc<int> new_idx;

  template <typename F>
  Wavelet_Matrix_2D_Range(int n, F f) {
    build(n, f);
  }

  template <typename F>
  void build(int m, F f) {
    n = m;
    vc<XY> X(n), Y(n);
    vc<T> S(n);
    FOR(i, n) {
      auto tmp = f(i);
      X[i] = get<0>(tmp), Y[i] = get<1>(tmp), S[i] = get<2>(tmp);
    }
    new_idx = IDX_X.build(X);
    vc<int> I(n);
    FOR(i, n) I[new_idx[i]] = i;
    Y = rearrange(Y, I);
    S = rearrange(S, I);
    WM.build(n, [&](int i) -> pair<XY, T> { return {Y[i], S[i]}; });
  }

  int count(XY x1, XY x2, XY y1, XY y2) {
    return WM.count(IDX_X(x1), IDX_X(x2), y1, y2);
  }

  // [L,R) x [-inf,y)
  pair<int, T> prefix_count_and_prod(XY x1, XY x2, XY y) {
    return WM.prefix_count_and_prod(IDX_X(x1), IDX_X(x2), y);
  }

  // [L,R) x [y1,y2)
  pair<int, T> count_and_prod(XY x1, XY x2, XY y1, XY y2) {
    return WM.count_and_prod(IDX_X(x1), IDX_X(x2), y1, y2);
  }

  // [L,R) x [-inf,inf)
  T prod_all(XY x1, XY x2) { return WM.prod_all(IDX_X(x1), IDX_X(x2)); }
  // [L,R) x [-inf,y)
  T prefix_prod(XY x1, XY x2, XY y) {
    return WM.prefix_prod(IDX_X(x1), IDX_X(x2), y);
  }
  // [L,R) x [y1,y2)
  T prod(XY x1, XY x2, XY y1, XY y2) {
    return WM.prod(IDX_X(x1), IDX_X(x2), y1, y2);
  }
  // i は最初に渡したインデックス
  void set(int i, T t) { WM.set(new_idx[i], t); }
  // i は最初に渡したインデックス
  void multiply(int i, T t) { WM.multiply(new_idx[i], t); }
  void add(int i, T t) { WM.multiply(new_idx[i], t); }
};
Back to top page