competitive-programming-library
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
old/segment-tree-2d.inc.cpp
- View this file on GitHub
- Last update: 2020-01-08 18:35:19+09:00
Code
/**
* @note O(h * w) space
*/
template <class CommutativeMonoid>
struct segment_tree_2d {
typedef typename CommutativeMonoid::value_type value_type;
int h1, w1;
int h, w;
vector<value_type> data;
CommutativeMonoid mon;
segment_tree_2d() = default;
segment_tree_2d(int h_, int w_, value_type initial_value = CommutativeMonoid().unit(), CommutativeMonoid const & mon_ = CommutativeMonoid())
: h1(h_), w1(w_), mon(mon_) {
h = pow(2, ceil(log2(h_)));
w = pow(2, ceil(log2(w_)));
data.resize((2 * h - 1) * (2 * w - 1), mon.unit());
REP_R (y, h) REP_R (x, w) {
if (y < h - 1) {
at(y, x) = mon.append(
at(2 * y + 1, x),
at(2 * y + 2, x));
} else if (x < w - 1) {
at(y, x) = mon.append(
at(y, 2 * x + 1),
at(y, 2 * x + 2));
} else if (y < h - 1 + h_ and x < w - 1 + w_) {
at(y, x) = initial_value;
}
}
}
inline value_type & at(int y, int x) {
return data[y * (2 * w - 1) + x];
}
inline value_type const & at(int y, int x) const {
return data[y * (2 * w - 1) + x];
}
/**
* @note O(log h * log w)
*/
void point_set(int y, int x, value_type value) {
assert (0 <= y and y < h1 and 0 <= x and x < w1);
for (int i = y + h; i > 0; i /= 2) { // 1-based
for (int j = x + w; j > 0; j /= 2) { // 1-based
if (i >= h and j >= w) {
at(i - 1, j - 1) = value;
} else if (j >= w) {
at(i - 1, j - 1) = mon.append(
at(2 * i - 1, j - 1),
at(2 * i, j - 1));
} else {
at(i - 1, j - 1) = mon.append(
at(i - 1, 2 * j - 1),
at(i - 1, 2 * j));
}
}
}
}
/**
* @note O(log h * log w)
*/
value_type area_concat(int ly, int lx, int ry, int rx) const {
assert (0 <= ly and ly <= ry and ry <= h1);
assert (0 <= lx and lx <= rx and rx <= w1);
return area_concat(0, 0, 0, 0, h, w, false, ly, lx, ry, rx);
}
value_type area_concat(int i, int j, int ily, int jlx, int iry, int jrx, bool p, int ly, int lx, int ry, int rx) const {
if (iry <= ly or ry <= ily or jrx <= lx or rx <= jlx) {
return mon.unit();
} else if (ly <= ily and iry <= ry and lx <= jlx and jrx <= rx) {
return at(i, j);
} else if ((ly <= ily and iry <= ry) or (p and not (lx <= jlx and jrx <= rx))) {
return mon.append(
area_concat(i, 2 * j + 1, ily, jlx, iry, (jlx + jrx) / 2, not p, ly, lx, ry, rx),
area_concat(i, 2 * j + 2, ily, (jlx + jrx) / 2, iry, jrx, not p, ly, lx, ry, rx));
} else {
return mon.append(
area_concat(2 * i + 1, j, ily, jlx, (ily + iry) / 2, jrx, not p, ly, lx, ry, rx),
area_concat(2 * i + 2, j, (ily + iry) / 2, jlx, iry, jrx, not p, ly, lx, ry, rx));
}
}
/**
* @note call area_concat O((ry - ly) / h * (rx - lx) / w) times
*/
value_type area_concat_torus(int ly, int lx, int ry, int rx) const {
value_type acc = mon.unit();
while (ly < 0) { ly += h1; ry += h1; }
while (lx < 0) { lx += w1; rx += w1; }
for (int bi = ly / h1; bi <= (ry - 1) / h1; ++ bi) {
int ly1 = (bi == ly / h1 ? ly % h1 : 0);
int ry1 = (bi == ry / h1 ? ry % h1 : h1);
for (int bj = lx / w1; bj <= (rx - 1) / w1; ++ bj) {
int lx1 = (bj == lx / w1 ? lx % w1 : 0);
int rx1 = (bj == rx / w1 ? rx % w1 : w1);
acc = mon.append(acc, area_concat(ly1, lx1, ry1, rx1));
}
}
return acc;
}
};
struct max_monoid {
typedef int value_type;
int unit() const { return INT_MIN; }
int append(int a, int b) const { return max(a, b); }
};
struct plus_monoid {
typedef int value_type;
int unit() const { return 0; }
int append(int a, int b) const { return a + b; }
};
unittest {
default_random_engine gen;
REP (iteration, 100) {
int h = uniform_int_distribution<int>(1, 30)(gen);
int w = uniform_int_distribution<int>(1, 30)(gen);
vector<vector<int> > a(h, vector<int>(w));
segment_tree_2d<plus_monoid> segtree(h, w);
REP (y, h) REP (x, w) {
a[y][x] = uniform_int_distribution<int>(-10, 10)(gen);
segtree.point_set(y, x, a[y][x]);
}
REP (y, h) REP (x, w) {
assert (a[y][x] == segtree.area_concat(y, x, y + 1, x + 1));
}
REP (iteration, 100) {
int ly = uniform_int_distribution<int>(0, h - 1)(gen);
int lx = uniform_int_distribution<int>(0, w - 1)(gen);
int ry = uniform_int_distribution<int>(ly + 1, h)(gen);
int rx = uniform_int_distribution<int>(lx + 1, w)(gen);
int acc = 0;
REP3 (y, ly, ry) {
REP3 (x, lx, rx) {
acc += a[y][x];
}
}
assert (acc == segtree.area_concat(ly, lx, ry, rx));
}
REP (iteration, 10) {
int ly = uniform_int_distribution<int>(- 100, 50)(gen);
int lx = uniform_int_distribution<int>(- 100, 50)(gen);
int ry = uniform_int_distribution<int>(ly, 100)(gen);
int rx = uniform_int_distribution<int>(lx, 100)(gen);
int acc = 0;
REP3 (y, ly, ry) {
REP3 (x, lx, rx) {
acc += a[(y % h + h) % h][(x % w + w) % w];
}
}
assert (acc == segtree.area_concat_torus(ly, lx, ry, rx));
}
}
}#line 1 "old/segment-tree-2d.inc.cpp"
/**
* @note O(h * w) space
*/
template <class CommutativeMonoid>
struct segment_tree_2d {
typedef typename CommutativeMonoid::value_type value_type;
int h1, w1;
int h, w;
vector<value_type> data;
CommutativeMonoid mon;
segment_tree_2d() = default;
segment_tree_2d(int h_, int w_, value_type initial_value = CommutativeMonoid().unit(), CommutativeMonoid const & mon_ = CommutativeMonoid())
: h1(h_), w1(w_), mon(mon_) {
h = pow(2, ceil(log2(h_)));
w = pow(2, ceil(log2(w_)));
data.resize((2 * h - 1) * (2 * w - 1), mon.unit());
REP_R (y, h) REP_R (x, w) {
if (y < h - 1) {
at(y, x) = mon.append(
at(2 * y + 1, x),
at(2 * y + 2, x));
} else if (x < w - 1) {
at(y, x) = mon.append(
at(y, 2 * x + 1),
at(y, 2 * x + 2));
} else if (y < h - 1 + h_ and x < w - 1 + w_) {
at(y, x) = initial_value;
}
}
}
inline value_type & at(int y, int x) {
return data[y * (2 * w - 1) + x];
}
inline value_type const & at(int y, int x) const {
return data[y * (2 * w - 1) + x];
}
/**
* @note O(log h * log w)
*/
void point_set(int y, int x, value_type value) {
assert (0 <= y and y < h1 and 0 <= x and x < w1);
for (int i = y + h; i > 0; i /= 2) { // 1-based
for (int j = x + w; j > 0; j /= 2) { // 1-based
if (i >= h and j >= w) {
at(i - 1, j - 1) = value;
} else if (j >= w) {
at(i - 1, j - 1) = mon.append(
at(2 * i - 1, j - 1),
at(2 * i, j - 1));
} else {
at(i - 1, j - 1) = mon.append(
at(i - 1, 2 * j - 1),
at(i - 1, 2 * j));
}
}
}
}
/**
* @note O(log h * log w)
*/
value_type area_concat(int ly, int lx, int ry, int rx) const {
assert (0 <= ly and ly <= ry and ry <= h1);
assert (0 <= lx and lx <= rx and rx <= w1);
return area_concat(0, 0, 0, 0, h, w, false, ly, lx, ry, rx);
}
value_type area_concat(int i, int j, int ily, int jlx, int iry, int jrx, bool p, int ly, int lx, int ry, int rx) const {
if (iry <= ly or ry <= ily or jrx <= lx or rx <= jlx) {
return mon.unit();
} else if (ly <= ily and iry <= ry and lx <= jlx and jrx <= rx) {
return at(i, j);
} else if ((ly <= ily and iry <= ry) or (p and not (lx <= jlx and jrx <= rx))) {
return mon.append(
area_concat(i, 2 * j + 1, ily, jlx, iry, (jlx + jrx) / 2, not p, ly, lx, ry, rx),
area_concat(i, 2 * j + 2, ily, (jlx + jrx) / 2, iry, jrx, not p, ly, lx, ry, rx));
} else {
return mon.append(
area_concat(2 * i + 1, j, ily, jlx, (ily + iry) / 2, jrx, not p, ly, lx, ry, rx),
area_concat(2 * i + 2, j, (ily + iry) / 2, jlx, iry, jrx, not p, ly, lx, ry, rx));
}
}
/**
* @note call area_concat O((ry - ly) / h * (rx - lx) / w) times
*/
value_type area_concat_torus(int ly, int lx, int ry, int rx) const {
value_type acc = mon.unit();
while (ly < 0) { ly += h1; ry += h1; }
while (lx < 0) { lx += w1; rx += w1; }
for (int bi = ly / h1; bi <= (ry - 1) / h1; ++ bi) {
int ly1 = (bi == ly / h1 ? ly % h1 : 0);
int ry1 = (bi == ry / h1 ? ry % h1 : h1);
for (int bj = lx / w1; bj <= (rx - 1) / w1; ++ bj) {
int lx1 = (bj == lx / w1 ? lx % w1 : 0);
int rx1 = (bj == rx / w1 ? rx % w1 : w1);
acc = mon.append(acc, area_concat(ly1, lx1, ry1, rx1));
}
}
return acc;
}
};
struct max_monoid {
typedef int value_type;
int unit() const { return INT_MIN; }
int append(int a, int b) const { return max(a, b); }
};
struct plus_monoid {
typedef int value_type;
int unit() const { return 0; }
int append(int a, int b) const { return a + b; }
};
unittest {
default_random_engine gen;
REP (iteration, 100) {
int h = uniform_int_distribution<int>(1, 30)(gen);
int w = uniform_int_distribution<int>(1, 30)(gen);
vector<vector<int> > a(h, vector<int>(w));
segment_tree_2d<plus_monoid> segtree(h, w);
REP (y, h) REP (x, w) {
a[y][x] = uniform_int_distribution<int>(-10, 10)(gen);
segtree.point_set(y, x, a[y][x]);
}
REP (y, h) REP (x, w) {
assert (a[y][x] == segtree.area_concat(y, x, y + 1, x + 1));
}
REP (iteration, 100) {
int ly = uniform_int_distribution<int>(0, h - 1)(gen);
int lx = uniform_int_distribution<int>(0, w - 1)(gen);
int ry = uniform_int_distribution<int>(ly + 1, h)(gen);
int rx = uniform_int_distribution<int>(lx + 1, w)(gen);
int acc = 0;
REP3 (y, ly, ry) {
REP3 (x, lx, rx) {
acc += a[y][x];
}
}
assert (acc == segtree.area_concat(ly, lx, ry, rx));
}
REP (iteration, 10) {
int ly = uniform_int_distribution<int>(- 100, 50)(gen);
int lx = uniform_int_distribution<int>(- 100, 50)(gen);
int ry = uniform_int_distribution<int>(ly, 100)(gen);
int rx = uniform_int_distribution<int>(lx, 100)(gen);
int acc = 0;
REP3 (y, ly, ry) {
REP3 (x, lx, rx) {
acc += a[(y % h + h) % h][(x % w + w) % w];
}
}
assert (acc == segtree.area_concat_torus(ly, lx, ry, rx));
}
}
}