library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/rectangle_sum.test.cpp

Depends on

Code

#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";
}
Back to top page