lmori's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
data-structure/wavelet-matrix/query/RectangleAddPointGet.hpp
- View this file on GitHub
- Last update: 2025-05-12 11:31:04+09:00
- Include:
#include "data-structure/wavelet-matrix/query/RectangleAddPointGet.hpp"
Depends on
- Wavelet Matrix (BIT)
(data-structure/wavelet-matrix/WaveletMatrixBinaryIndexedTree.hpp)
- data-structure/wavelet-matrix/query/PointAddRectangleSum.hpp
Code
#include "./PointAddRectangleSum.hpp"
template <class S>
class RectangleAddPointGet {
private:
vector<S> x1, y1, x2, y2, w;
vector<vector<S>> q;
int add_query = 0;
int output_query = 0;
int dft;
public:
RectangleAddPointGet() {}
RectangleAddPointGet(int query) {
q = vector<vector<S>>(query, vector<S>(3));
}
RectangleAddPointGet(const vector<S> &lx, const vector<S> &ly, const vector<S> &rx, const vector<S> &ry, const vector<S> &vw, int query) {
q = vector<vector<S>>(query, vector<S>(3));
int n = lx.size();
dft = n;
x1.assign(n * 4, 0);
y1.assign(n * 4, 0);
w.assign(n * 4, 0);
for (int i = 0; i < n; i++) {
x1[i * 4] = lx[i];
y1[i * 4] = ly[i];
x1[i * 4 + 1] = rx[i];
y1[i * 4 + 1] = ly[i];
x1[i * 4 + 2] = lx[i];
y1[i * 4 + 2] = ry[i];
x1[i * 4 + 3] = rx[i];
y1[i * 4 + 3] = ry[i];
w[i * 4] = vw[i];
w[i * 4 + 1] = -vw[i];
w[i * 4 + 2] = -vw[i];
w[i * 4 + 3] = vw[i];
}
}
void rectangle_add(S lx, S ly, S rx, S ry, S weight) {
int cur = add_query + output_query;
q[cur][0] = 0;
q[cur][1] = weight;
x1.emplace_back(lx);
y1.emplace_back(ly);
x1.emplace_back(rx);
y1.emplace_back(ly);
x1.emplace_back(lx);
y1.emplace_back(ry);
x1.emplace_back(rx);
y1.emplace_back(ry);
for (int i = 0; i < 4; i++) {
w.emplace_back(0);
}
add_query++;
}
void get(S x, S y) {
int cur = add_query + output_query;
q[cur][0] = 1;
q[cur][1] = x + 1;
q[cur][2] = y + 1;
output_query++;
}
vector<S> build() {
PointAddRectangleSum<S> wm(x1, y1, w, add_query * 4 + output_query);
int cnt = dft * 4;
for (int i = 0; i < output_query + add_query; i++) {
S com = q[i][0];
if (com == 0) {
wm.add(x1[cnt], y1[cnt], q[i][1]);
wm.add(x1[cnt + 1], y1[cnt + 1], -q[i][1]);
wm.add(x1[cnt + 2], y1[cnt + 2], -q[i][1]);
wm.add(x1[cnt + 3], y1[cnt + 3], q[i][1]);
cnt += 4;
} else {
wm.rectangle_sum(0, 0, q[i][1], q[i][2]);
}
}
return wm.build();
}
};#line 1 "data-structure/wavelet-matrix/WaveletMatrixBinaryIndexedTree.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<fenwick_tree<S>> fen;
vector<unsigned> zero;
vector<T> cmp;
T MI, MA;
inline unsigned compress(const T &x) {
return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
}
public:
// コンストラクタ
WaveletMatrix() {}
WaveletMatrix(vector<T> v) {
MI = numeric_limits<T>::min();
MA = numeric_limits<T>::max();
n = v.size();
cmp = v;
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
vector<T> tmp(n);
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);
zero.resize(bitsize, 0);
int cur = 0;
for (unsigned i = 0; i < bitsize; i++) {
b[i] = BitVector(n + 1);
fen[i] = fenwick_tree<T>(n);
cur = 0;
for (unsigned j = 0; j < n; j++) {
fen[i].add(j, v[j]);
if (compressed[j] & (1U << (bitsize - i - 1))) {
b[i].set(j);
} else {
zero[i]++;
tmpc[cur] = compressed[j];
tmp[cur] = v[j];
cur++;
}
}
b[i].build();
for (int j = 0; j < n; j++) {
if (compressed[j] & (1U << (bitsize - i - 1))) {
tmpc[cur] = compressed[j];
tmp[cur] = v[j];
cur++;
}
}
swap(tmpc, compressed);
swap(tmp, v);
}
b[bitsize] = BitVector(n + 1);
fen[bitsize] = fenwick_tree<T>(n);
for (unsigned i = 0; i < n; i++) {
fen[bitsize].add(i, v[i]);
}
}
WaveletMatrix(vector<T> v, vector<S> w) {
MI = numeric_limits<T>::min();
MA = numeric_limits<T>::max();
n = v.size();
cmp = v;
sort(cmp.begin(), cmp.end());
cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
vector<S> tmp(n);
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);
zero.resize(bitsize, 0);
int cur = 0;
for (unsigned i = 0; i < bitsize; i++) {
b[i] = BitVector(n + 1);
fen[i] = fenwick_tree<S>(n);
cur = 0;
for (unsigned j = 0; j < n; j++) {
fen[i].add(j, w[j]);
if (compressed[j] & (1U << (bitsize - i - 1))) {
b[i].set(j);
} else {
zero[i]++;
tmpc[cur] = compressed[j];
tmp[cur] = w[j];
cur++;
}
}
b[i].build();
for (int j = 0; j < n; j++) {
if (compressed[j] & (1U << (bitsize - i - 1))) {
tmpc[cur] = compressed[j];
tmp[cur] = w[j];
cur++;
}
}
swap(tmpc, compressed);
swap(tmp, w);
}
b[bitsize] = BitVector(n + 1);
fen[bitsize] = fenwick_tree<S>(n);
for (unsigned i = 0; i < n; i++) {
fen[bitsize].add(i, w[i]);
}
}
void set(int p, S x) {
unsigned cur = p;
S before = fen[0].get(p);
for (unsigned i = 0; i < bitsize; i++) {
fen[i].add(cur, x - before);
if (b[i].access(cur)) {
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
fen[bitsize].add(cur, x - before);
}
void add(int p, S x) {
unsigned cur = p;
for (unsigned i = 0; i < bitsize; i++) {
fen[i].add(cur, x);
if (b[i].access(cur)) {
cur = zero[i] + b[i].rank(cur);
} else {
cur -= b[i].rank(cur);
}
}
fen[bitsize].add(cur, x);
}
S get(int p) {
return fen[0].get(p);
}
// v[l,r) の中で[mink,maxk)に入る値の総和を返す
S range_sum(int vl, int vr, T mink, T maxk) {
int D = compress(mink);
int U = compress(maxk);
S res = 0;
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) {
res += fen[d].sum(L, R);
return;
}
if (d == bitsize) {
if (D <= A and A < U) {
res += fen[bitsize].sum(L, R);
}
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, vl, vr, 0, 1 << bitsize);
return res;
}
};
#line 2 "data-structure/wavelet-matrix/query/PointAddRectangleSum.hpp"
template <class S>
class PointAddRectangleSum {
private:
const int RESERVE = 700000;
const int QSIZE = 700000;
WaveletMatrix<S> wm;
vector<S> x, y, w;
vector<vector<S>> q;
int add_query = 0;
int output_query = 0;
int setidx;
public:
PointAddRectangleSum() {
x.reserve(RESERVE);
y.reserve(RESERVE);
w.reserve(RESERVE);
q.resize(QSIZE);
for (int i = 0; i < QSIZE; i++) {
q[i].assign(5, 0);
}
setidx = 0;
}
PointAddRectangleSum(int query) {
q = vector<vector<S>>(query, vector<S>(5));
setidx = 0;
}
PointAddRectangleSum(const vector<S> &vx, const vector<S> &vy, const vector<S> &vw, int query) {
q = vector<vector<S>>(query, vector<S>(5));
x = vx;
y = vy;
w = vw;
setidx = x.size();
}
void add(S px, S py, S weight) {
int cur = add_query + output_query;
q[cur][0] = 0;
q[cur][1] = px;
q[cur][2] = py;
q[cur][3] = weight;
q[cur][4] = setidx++;
x.emplace_back(px);
y.emplace_back(py);
w.emplace_back(0);
add_query++;
}
void rectangle_sum(S x1, S y1, S x2, S y2) {
int cur = add_query + output_query;
q[cur][0] = 1;
q[cur][1] = x1;
q[cur][2] = y1;
q[cur][3] = x2;
q[cur][4] = y2;
output_query++;
}
vector<S> build() {
wm = WaveletMatrix<S>(x, y, w);
vector<S> ret(output_query);
int idx = 0;
for (int i = 0; i < output_query + add_query; i++) {
S com = q[i][0];
if (com == 0) {
wm.set(q[i][4], q[i][3]);
} else {
ret[idx] = (wm.rectangle_sum(q[i][1], q[i][3], q[i][2], q[i][4]));
idx++;
}
}
return ret;
}
};
#line 2 "data-structure/wavelet-matrix/query/RectangleAddPointGet.hpp"
template <class S>
class RectangleAddPointGet {
private:
vector<S> x1, y1, x2, y2, w;
vector<vector<S>> q;
int add_query = 0;
int output_query = 0;
int dft;
public:
RectangleAddPointGet() {}
RectangleAddPointGet(int query) {
q = vector<vector<S>>(query, vector<S>(3));
}
RectangleAddPointGet(const vector<S> &lx, const vector<S> &ly, const vector<S> &rx, const vector<S> &ry, const vector<S> &vw, int query) {
q = vector<vector<S>>(query, vector<S>(3));
int n = lx.size();
dft = n;
x1.assign(n * 4, 0);
y1.assign(n * 4, 0);
w.assign(n * 4, 0);
for (int i = 0; i < n; i++) {
x1[i * 4] = lx[i];
y1[i * 4] = ly[i];
x1[i * 4 + 1] = rx[i];
y1[i * 4 + 1] = ly[i];
x1[i * 4 + 2] = lx[i];
y1[i * 4 + 2] = ry[i];
x1[i * 4 + 3] = rx[i];
y1[i * 4 + 3] = ry[i];
w[i * 4] = vw[i];
w[i * 4 + 1] = -vw[i];
w[i * 4 + 2] = -vw[i];
w[i * 4 + 3] = vw[i];
}
}
void rectangle_add(S lx, S ly, S rx, S ry, S weight) {
int cur = add_query + output_query;
q[cur][0] = 0;
q[cur][1] = weight;
x1.emplace_back(lx);
y1.emplace_back(ly);
x1.emplace_back(rx);
y1.emplace_back(ly);
x1.emplace_back(lx);
y1.emplace_back(ry);
x1.emplace_back(rx);
y1.emplace_back(ry);
for (int i = 0; i < 4; i++) {
w.emplace_back(0);
}
add_query++;
}
void get(S x, S y) {
int cur = add_query + output_query;
q[cur][0] = 1;
q[cur][1] = x + 1;
q[cur][2] = y + 1;
output_query++;
}
vector<S> build() {
PointAddRectangleSum<S> wm(x1, y1, w, add_query * 4 + output_query);
int cnt = dft * 4;
for (int i = 0; i < output_query + add_query; i++) {
S com = q[i][0];
if (com == 0) {
wm.add(x1[cnt], y1[cnt], q[i][1]);
wm.add(x1[cnt + 1], y1[cnt + 1], -q[i][1]);
wm.add(x1[cnt + 2], y1[cnt + 2], -q[i][1]);
wm.add(x1[cnt + 3], y1[cnt + 3], q[i][1]);
cnt += 4;
} else {
wm.rectangle_sum(0, 0, q[i][1], q[i][2]);
}
}
return wm.build();
}
};