lmori's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub lmorinn/library

:warning: Rectangle Add Point Get
(data-structure/wavelet-matrix/rectangle/RectangleAddPointGet.hpp)

概要

ウェーブレット行列 (+ 双対BIT) を拡張して、2次元平面のクエリに答えられるようにしたデータ構造。

事前に与えられた点の重みに対して矩形加算 / 一点取得が可能。

コンストラクタ

WaveletMatrix<S, T> wm(vector<T> x, vector<T> y, vector<S> w)

$i$ 番目の点の座標を $(x_i, y_i)$、重みを $w_i$ として、データ構造を構築する。

制約

計算量

rectangle_add

void wm.rectangle_add(T lx, T rx, T ly, T ry, S x)

矩形領域 $lx \leq x \lt rx$ かつ $ly \leq y \lt ry$ 内の点の重みに x を加算する。

制約

計算量

get

S wm.get(int p)

p 番目の点の重みを返す。

制約

計算量

Depends on

Code

#include "../WaveletMatrixDualBinaryIndexedTree.hpp"

template <class S, class T>
class RectangleAddPointGet {
   private:
    WaveletMatrix<S, T> wm;
    vector<T> px;
    vector<int> ord;

   public:
    RectangleAddPointGet() {}
    RectangleAddPointGet(vector<T> x, vector<T> y, vector<S> w) {
        int n = int(x.size());
        ord.resize(n);
        vector<tuple<T, T, S, int>> v(n);
        for (int i = 0; i < n; i++) v[i] = {x[i], y[i], w[i], i};
        sort(v.begin(), v.end(), [](const auto &a, const auto &b) {
            return std::get<0>(a) < std::get<0>(b);
        });
        px.resize(n);
        for (int i = 0; i < n; i++) {
            px[i] = std::get<0>(v[i]);
            y[i] = std::get<1>(v[i]);
            w[i] = std::get<2>(v[i]);
            ord[std::get<3>(v[i])] = i;
        }
        wm = WaveletMatrix<S, T>(y, w);
    }

    void rectangle_add(T xl, T xr, T yl, T yr, S x) {
        int l = distance(px.begin(), lower_bound(px.begin(), px.end(), xl));
        int r = distance(px.begin(), lower_bound(px.begin(), px.end(), xr));
        wm.range_add(l, r, yl, yr, x);
    }

    S get(int p) {
        return wm.get(ord[p]);
    }
};
#line 1 "data-structure/binary-indexed-tree/DualBinaryIndexedTree.hpp"
template <class T>
struct RangeAddPointGet {
   private:
    fenwick_tree<T> ft;

   public:
    RangeAddPointGet() {}
    RangeAddPointGet(int siz) : ft(siz + 1) {}

    void range_add(int l, int r, T x) {
        ft.add(l, x);
        ft.add(r, -x);
    }

    void add(int p, T x) {
        ft.add(p, x);
        ft.add(p + 1, -x);
    }

    T point_get(int p) {
        return ft.sum(0, p + 1);
    }
};
#line 2 "data-structure/wavelet-matrix/WaveletMatrixDualBinaryIndexedTree.hpp"
struct BitVector {
  unsigned sz;
  unsigned blocksize;
  vector<unsigned> bit, sum;

  BitVector() {}

  BitVector(unsigned siz) {
    sz = siz;
    blocksize = (sz + 31) >> 5;
    bit.assign(blocksize, 0U);
    sum.assign(blocksize, 0U);
  }

  inline void set(int k) { bit[k >> 5] |= 1U << (k & 31); }

  inline void build() {
    sum[0] = 0U;
    for (int i = 1; i < blocksize; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  inline bool access(unsigned k) {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  inline int rank(int k) {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }
};

template <class S, class T>
class WaveletMatrix {
 private:
  unsigned n;
  unsigned bitsize;
  vector<BitVector> b;
  vector<unsigned> zero;
  vector<T> cmp;
  vector<S> arr;
  vector<RangeAddPointGet<S>> fen;

  inline unsigned compress(const T &x) {
    return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
  }

 public:
  // コンストラクタ
  WaveletMatrix() {}

  WaveletMatrix(vector<T> v) {
    n = v.size();
    arr = v;
    cmp = v;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    vector<T> tmpc(n);
    vector<T> compressed(n);
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
    }
    bitsize = bit_width(cmp.size());
    b.resize(bitsize + 1);
    fen.resize(bitsize + 1, RangeAddPointGet<S>(n));
    zero.resize(bitsize, 0);
    int cur = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      b[i] = BitVector(n + 1);
      cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          b[i].set(j);
        } else {
          zero[i]++;
          tmpc[cur] = compressed[j];
          cur++;
        }
      }
      b[i].build();
      for (int j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          tmpc[cur] = compressed[j];
          cur++;
        }
      }
      swap(tmpc, compressed);
    }
    b[bitsize] = BitVector(n + 1);
  }

  WaveletMatrix(vector<T> v, vector<S> w) {
    n = v.size();
    arr = w;
    cmp = v;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    vector<T> tmpc(n);
    vector<T> compressed(n);
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
    }
    bitsize = bit_width(cmp.size());
    fen.resize(bitsize + 1, RangeAddPointGet<S>(n));
    b.resize(bitsize + 1);
    zero.resize(bitsize, 0);
    int cur = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      b[i] = BitVector(n + 1);
      cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          b[i].set(j);
        } else {
          zero[i]++;
          tmpc[cur] = compressed[j];
          cur++;
        }
      }
      b[i].build();
      for (int j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          tmpc[cur] = compressed[j];
          cur++;
        }
      }
      swap(tmpc, compressed);
    }
    b[bitsize] = BitVector(n + 1);
  }

  S get(unsigned k) {
    S val = arr[k];
    unsigned cur = k;
    for (unsigned i = 0; i < bitsize; i++) {
      val += fen[i].point_get(cur);
      if (b[i].access(cur)) {
        cur = zero[i] + b[i].rank(cur);
      } else {
        cur -= b[i].rank(cur);
      }
    }
    val += fen[bitsize].point_get(cur);
    return val;
  }

  void range_add(int l, int r, T mink, T maxk, S x) {
    int D = compress(mink);
    int U = compress(maxk);
    auto dfs = [&](auto &rec, int d, int L, int R, int A, int B) -> void {
      if (U <= A or B <= D) return;
      if (D <= A and B <= U) {
        fen[d].range_add(L, R, x);
        return;
      }
      if (d == bitsize) {
        if (D <= A and A < U) {
          fen[bitsize].range_add(L, R, x);
        }
        return;
      }
      int C = (A + B) >> 1;
      int rank0_l = L - b[d].rank(L);
      int rank0_r = R - b[d].rank(R);
      int rank1_l = b[d].rank(L) + zero[d];
      int rank1_r = b[d].rank(R) + zero[d];
      rec(rec, d + 1, rank0_l, rank0_r, A, C);
      rec(rec, d + 1, rank1_l, rank1_r, C, B);
    };
    dfs(dfs, 0, l, r, 0, 1 << bitsize);
  }
};
#line 2 "data-structure/wavelet-matrix/rectangle/RectangleAddPointGet.hpp"

template <class S, class T>
class RectangleAddPointGet {
   private:
    WaveletMatrix<S, T> wm;
    vector<T> px;
    vector<int> ord;

   public:
    RectangleAddPointGet() {}
    RectangleAddPointGet(vector<T> x, vector<T> y, vector<S> w) {
        int n = int(x.size());
        ord.resize(n);
        vector<tuple<T, T, S, int>> v(n);
        for (int i = 0; i < n; i++) v[i] = {x[i], y[i], w[i], i};
        sort(v.begin(), v.end(), [](const auto &a, const auto &b) {
            return std::get<0>(a) < std::get<0>(b);
        });
        px.resize(n);
        for (int i = 0; i < n; i++) {
            px[i] = std::get<0>(v[i]);
            y[i] = std::get<1>(v[i]);
            w[i] = std::get<2>(v[i]);
            ord[std::get<3>(v[i])] = i;
        }
        wm = WaveletMatrix<S, T>(y, w);
    }

    void rectangle_add(T xl, T xr, T yl, T yr, S x) {
        int l = distance(px.begin(), lower_bound(px.begin(), px.end(), xl));
        int r = distance(px.begin(), lower_bound(px.begin(), px.end(), xr));
        wm.range_add(l, r, yl, yr, x);
    }

    S get(int p) {
        return wm.get(ord[p]);
    }
};
Back to top page