This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <tuple>
#include <utility>
#include <vector>
#include "datastructure/rectangle_sum.hpp"
int main() {
std::mt19937_64 rng(20261027);
for (int iter = 0; iter < 500; iter++) {
int n = rng() % 30;
long long range = 1 + rng() % 20;
std::vector<std::tuple<long long, long long, long long>> pts(n);
std::vector<std::pair<long long, long long>> pts2(n);
for (int i = 0; i < n; i++) {
long long x = (long long)(rng() % range) - range / 2;
long long y = (long long)(rng() % range) - range / 2;
long long w = (long long)(rng() % 2001) - 1000;
pts[i] = {x, y, w};
pts2[i] = {x, y};
}
rectangle_sum<long long, long long> rs(pts);
rectangle_sum<long long> rc(pts2);
assert(rs.size() == n && rc.size() == n);
for (int t = 0; t < 50; t++) {
long long x1 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long x2 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long y1 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long y2 = (long long)(rng() % (range + 2)) - range / 2 - 1;
int cnt = 0;
long long sum = 0;
for (auto [x, y, w] : pts) {
if (x1 <= x && x < x2 && y1 <= y && y < y2) cnt++, sum += w;
}
assert(rs.count(x1, x2, y1, y2) == cnt);
assert(rc.count(x1, x2, y1, y2) == cnt);
assert(rs.sum(x1, x2, y1, y2) == sum);
}
}
{
int n = 200000, q = 200000;
auto start = std::chrono::steady_clock::now();
std::vector<std::tuple<int, int, long long>> pts(n);
for (auto& [x, y, w] : pts) x = rng() % 1000000000, y = rng() % 1000000000, w = rng() % 1000000000;
rectangle_sum<int, long long> rs(pts);
long long acc = 0;
for (int i = 0; i < q; i++) {
int x1 = rng() % 1000000000, x2 = rng() % 1000000000;
int y1 = rng() % 1000000000, y2 = rng() % 1000000000;
if (x1 > x2) std::swap(x1, x2);
if (y1 > y2) std::swap(y1, y2);
acc = (acc + rs.sum(x1, x2, y1, y2)) % 1000000007;
}
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
}
std::cout << "Hello World\n";
}#line 1 "test/unit/rectangle_sum.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <tuple>
#include <utility>
#include <vector>
#line 2 "datastructure/rectangle_sum.hpp"
#include <algorithm>
#line 5 "datastructure/rectangle_sum.hpp"
#include <type_traits>
#line 8 "datastructure/rectangle_sum.hpp"
#line 3 "datastructure/wavelet_matrix.hpp"
#include <bit>
#line 5 "datastructure/wavelet_matrix.hpp"
#include <cstdint>
#include <optional>
#line 9 "datastructure/wavelet_matrix.hpp"
template <class T, class S = void> struct wavelet_matrix {
private:
using W = std::conditional_t<std::is_void_v<S>, int, S>;
static constexpr bool weighted = !std::is_void_v<S>;
public:
wavelet_matrix() {
build({}, {});
}
explicit wavelet_matrix(const std::vector<T>& a)
requires (!weighted)
{
build(a, {});
}
wavelet_matrix(const std::vector<T>& a, const std::vector<S>& w)
requires weighted
{
assert(a.size() == w.size());
build(a, w);
}
int size() const {
return n;
}
// #{ i in [l, r) : a[i] < upper }
int count(int l, int r, T upper) const {
assert(0 <= l && l <= r && r <= n);
return count_rank(l, r, rank_of(upper));
}
// #{ i in [l, r) : lower <= a[i] < upper }
int count(int l, int r, T lower, T upper) const {
assert(0 <= l && l <= r && r <= n);
int lo = rank_of(lower), hi = rank_of(upper);
if (lo >= hi) return 0;
return count_rank(l, r, hi) - count_rank(l, r, lo);
}
// k-th smallest (0-indexed) of a[l..r)
T kth_smallest(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k < r - l);
int res = 0;
for (int d = log - 1; d >= 0; d--) {
int l0 = bv[d].rank0(l), r0 = bv[d].rank0(r);
if (k < r0 - l0) {
l = l0, r = r0;
} else {
k -= r0 - l0;
res |= 1 << d;
l += bv[d].zeros - l0, r += bv[d].zeros - r0;
}
}
return key[res];
}
// k-th largest (0-indexed) of a[l..r)
T kth_largest(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k < r - l);
return kth_smallest(l, r, r - l - 1 - k);
}
// max { a[i] : i in [l, r), a[i] < upper }
std::optional<T> prev_value(int l, int r, T upper) const {
assert(0 <= l && l <= r && r <= n);
int c = count_rank(l, r, rank_of(upper));
if (c == 0) return std::nullopt;
return kth_smallest(l, r, c - 1);
}
// min { a[i] : i in [l, r), lower <= a[i] }
std::optional<T> next_value(int l, int r, T lower) const {
assert(0 <= l && l <= r && r <= n);
int c = count_rank(l, r, rank_of(lower));
if (c == r - l) return std::nullopt;
return kth_smallest(l, r, c);
}
// sum of w[i] over i in [l, r) with a[i] < upper
S sum(int l, int r, T upper) const
requires weighted
{
assert(0 <= l && l <= r && r <= n);
return sum_rank(l, r, rank_of(upper));
}
// sum of w[i] over i in [l, r) with lower <= a[i] < upper
S sum(int l, int r, T lower, T upper) const
requires weighted
{
assert(0 <= l && l <= r && r <= n);
int lo = rank_of(lower), hi = rank_of(upper);
if (lo >= hi) return S();
return sum_rank(l, r, hi) - sum_rank(l, r, lo);
}
// sum of w[i] over the k elements of a[l..r) with the smallest (a[i], i)
S sum_smallest(int l, int r, int k) const
requires weighted
{
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k <= r - l);
if (k == r - l) return cs[log][r] - cs[log][l];
S res = S();
for (int d = log - 1; d >= 0; d--) {
int l0 = bv[d].rank0(l), r0 = bv[d].rank0(r);
if (k < r0 - l0) {
l = l0, r = r0;
} else {
k -= r0 - l0;
res += cs[d][r0] - cs[d][l0];
l += bv[d].zeros - l0, r += bv[d].zeros - r0;
}
}
return res + cs[0][l + k] - cs[0][l];
}
private:
struct bit_vector {
std::vector<uint64_t> bits;
std::vector<int> cnt;
int zeros;
explicit bit_vector(int n) : bits(n / 64 + 1), cnt(n / 64 + 2), zeros(n) {
}
void set(int i) {
bits[i >> 6] |= uint64_t(1) << (i & 63);
}
void build() {
for (int i = 0; i < int(bits.size()); i++) {
cnt[i + 1] = cnt[i] + std::popcount(bits[i]);
}
zeros -= cnt.back();
}
int rank1(int i) const {
return cnt[i >> 6] +
std::popcount(bits[i >> 6] & ((uint64_t(1) << (i & 63)) - 1));
}
int rank0(int i) const {
return i - rank1(i);
}
};
int n, log;
std::vector<T> key;
std::vector<bit_vector> bv;
// cs[d]: prefix sums of weights in the order at level d (cs[log]: original order)
std::vector<std::vector<W>> cs;
void build(const std::vector<T>& a, const std::vector<W>& w) {
n = int(a.size());
key = a;
std::ranges::sort(key);
key.erase(std::ranges::unique(key).begin(), key.end());
log = key.empty() ? 0 : std::bit_width(unsigned(key.size() - 1));
std::vector<int> b(n), order(n);
for (int i = 0; i < n; i++) {
b[i] = int(std::ranges::lower_bound(key, a[i]) - key.begin());
order[i] = i;
}
bv.assign(log, bit_vector(n));
if constexpr (weighted) {
cs.assign(log + 1, std::vector<W>(n + 1));
for (int i = 0; i < n; i++) cs[log][i + 1] = cs[log][i] + w[i];
}
std::vector<int> next(n);
for (int d = log - 1; d >= 0; d--) {
int z = 0;
for (int i = 0; i < n; i++) {
if (b[order[i]] >> d & 1) {
bv[d].set(i);
} else {
next[z++] = order[i];
}
}
for (int i = 0; i < n; i++) {
if (b[order[i]] >> d & 1) next[z++] = order[i];
}
bv[d].build();
std::swap(order, next);
if constexpr (weighted) {
for (int i = 0; i < n; i++) cs[d][i + 1] = cs[d][i] + w[order[i]];
}
}
}
// #{ v in key : v < x }
int rank_of(const T& x) const {
return int(std::ranges::lower_bound(key, x) - key.begin());
}
// #{ i in [l, r) : b[i] < u }, 0 <= u <= |key|
int count_rank(int l, int r, int u) const {
if (u == 0) return 0;
if (u >= int(key.size())) return r - l;
int res = 0;
for (int d = log - 1; d >= 0; d--) {
int l0 = bv[d].rank0(l), r0 = bv[d].rank0(r);
if (u >> d & 1) {
res += r0 - l0;
l += bv[d].zeros - l0, r += bv[d].zeros - r0;
} else {
l = l0, r = r0;
}
}
return res;
}
S sum_rank(int l, int r, int u) const
requires weighted
{
if (u == 0) return S();
if (u >= int(key.size())) return cs[log][r] - cs[log][l];
S res = S();
for (int d = log - 1; d >= 0; d--) {
int l0 = bv[d].rank0(l), r0 = bv[d].rank0(r);
if (u >> d & 1) {
res += cs[d][r0] - cs[d][l0];
l += bv[d].zeros - l0, r += bv[d].zeros - r0;
} else {
l = l0, r = r0;
}
}
return res;
}
};
#line 10 "datastructure/rectangle_sum.hpp"
template <class T, class S = void> struct rectangle_sum {
private:
static constexpr bool weighted = !std::is_void_v<S>;
public:
rectangle_sum() {
}
explicit rectangle_sum(std::vector<std::pair<T, T>> points)
requires (!weighted)
{
std::ranges::sort(points);
int n = int(points.size());
std::vector<T> ys(n);
xs.resize(n);
for (int i = 0; i < n; i++) std::tie(xs[i], ys[i]) = points[i];
wm = wavelet_matrix<T, S>(ys);
}
explicit rectangle_sum(std::vector<std::tuple<T, T, S>> points)
requires weighted
{
std::ranges::sort(points, [](const auto& a, const auto& b) {
return std::get<0>(a) < std::get<0>(b);
});
int n = int(points.size());
std::vector<T> ys(n);
std::vector<S> ws(n);
xs.resize(n);
for (int i = 0; i < n; i++) std::tie(xs[i], ys[i], ws[i]) = points[i];
wm = wavelet_matrix<T, S>(ys, ws);
}
int size() const {
return int(xs.size());
}
int count(T x1, T x2, T y1, T y2) const {
auto [l, r] = range(x1, x2);
if (l >= r) return 0;
return wm.count(l, r, y1, y2);
}
S sum(T x1, T x2, T y1, T y2) const
requires weighted
{
auto [l, r] = range(x1, x2);
if (l >= r) return S();
return wm.sum(l, r, y1, y2);
}
private:
std::vector<T> xs;
wavelet_matrix<T, S> wm;
std::pair<int, int> range(T x1, T x2) const {
int l = int(std::ranges::lower_bound(xs, x1) - xs.begin());
int r = int(std::ranges::lower_bound(xs, x2) - xs.begin());
return {l, r};
}
};
#line 11 "test/unit/rectangle_sum.test.cpp"
int main() {
std::mt19937_64 rng(20261027);
for (int iter = 0; iter < 500; iter++) {
int n = rng() % 30;
long long range = 1 + rng() % 20;
std::vector<std::tuple<long long, long long, long long>> pts(n);
std::vector<std::pair<long long, long long>> pts2(n);
for (int i = 0; i < n; i++) {
long long x = (long long)(rng() % range) - range / 2;
long long y = (long long)(rng() % range) - range / 2;
long long w = (long long)(rng() % 2001) - 1000;
pts[i] = {x, y, w};
pts2[i] = {x, y};
}
rectangle_sum<long long, long long> rs(pts);
rectangle_sum<long long> rc(pts2);
assert(rs.size() == n && rc.size() == n);
for (int t = 0; t < 50; t++) {
long long x1 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long x2 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long y1 = (long long)(rng() % (range + 2)) - range / 2 - 1;
long long y2 = (long long)(rng() % (range + 2)) - range / 2 - 1;
int cnt = 0;
long long sum = 0;
for (auto [x, y, w] : pts) {
if (x1 <= x && x < x2 && y1 <= y && y < y2) cnt++, sum += w;
}
assert(rs.count(x1, x2, y1, y2) == cnt);
assert(rc.count(x1, x2, y1, y2) == cnt);
assert(rs.sum(x1, x2, y1, y2) == sum);
}
}
{
int n = 200000, q = 200000;
auto start = std::chrono::steady_clock::now();
std::vector<std::tuple<int, int, long long>> pts(n);
for (auto& [x, y, w] : pts) x = rng() % 1000000000, y = rng() % 1000000000, w = rng() % 1000000000;
rectangle_sum<int, long long> rs(pts);
long long acc = 0;
for (int i = 0; i < q; i++) {
int x1 = rng() % 1000000000, x2 = rng() % 1000000000;
int y1 = rng() % 1000000000, y2 = rng() % 1000000000;
if (x1 > x2) std::swap(x1, x2);
if (y1 > y2) std::swap(y1, y2);
acc = (acc + rs.sum(x1, x2, y1, y2)) % 1000000007;
}
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
std::cerr << "perf n=q=" << n << ": " << ms << " ms (" << acc % 1000 << ")\n";
}
std::cout << "Hello World\n";
}