test/unit/range_map.test.cpp

• View this file on GitHub
• Last update: 2026-10-19 22:21:29+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• Range Map (datastructure/range_map.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <map>
#include <optional>
#include <random>
#include <vector>

#include "datastructure/range_map.hpp"
void stress(std::mt19937& rng) {
    const int U = 1 + rng() % 30;
    const int K = 1 + rng() % 4;  // 値の種類
    const int NONE = -1;
    std::vector<int> a(U, NONE);
    range_map<int, int> mp;
    std::map<int, long long> cnt;  // コールバックで管理する値ごとの個数
    long long runs = 0;            // コールバックで管理する run の個数
    auto f = [&](int l, int r, const int& x) {
        cnt[x] += r - l;
        runs++;
    };
    auto g = [&](int l, int r, const int& x) {
        cnt[x] -= r - l;
        runs--;
    };
    for (int it = 0; it < 200; it++) {
        int l = rng() % U, r = rng() % U;
        if (l > r) std::swap(l, r);
        r++;
        if (rng() % 3) {
            int x = rng() % K;
            mp.assign(l, r, x, f, g);
            for (int i = l; i < r; i++) a[i] = x;
        } else {
            mp.erase(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = NONE;
        }
        // 値と contains
        for (int p = 0; p < U; p++) {
            auto fi = mp.find(p);
            assert(mp.contains(p) == (a[p] != NONE));
            if (a[p] != NONE) {
                assert(fi != mp.end() && fi->l <= p && p < fi->r && fi->x == a[p]);
            } else {
                assert(fi == mp.end());
            }
        }
        // run が正規形: 値のある極大な連続区間と一致
        int expect_runs = 0;
        for (int p = 0; p < U; p++) expect_runs += a[p] != NONE && (p == 0 || a[p] != a[p - 1]);
        assert(mp.size() == expect_runs);
        assert(runs == expect_runs);
        int prev_r = -1;
        std::optional<int> prev_x;
        for (auto [rl, rr, rx] : mp) {
            assert(rl < rr);
            assert(prev_r <= rl);
            if (prev_r == rl) assert(*prev_x != rx);
            for (int p = rl; p < rr; p++) assert(a[p] == rx);
            if (rl > 0) assert(a[rl - 1] != rx);
            if (rr < U) assert(a[rr] != rx);
            prev_r = rr;
            prev_x = rx;
        }
        // ヒストグラム
        std::map<int, long long> expect;
        for (int v : a) {
            if (v != NONE) expect[v]++;
        }
        for (auto [v, c] : cnt) assert(c == expect[v]);
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 300; trial++) stress(rng);
    std::cout << "Hello World" << std::endl;
    return 0;
}

#line 1 "test/unit/range_map.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <map>
#include <optional>
#include <random>
#include <vector>

#line 3 "datastructure/range_map.hpp"
#include <iterator>
#line 5 "datastructure/range_map.hpp"
#include <set>
template <class T, class S>
struct range_map {
public:
    struct run {
        T l, r;
        S x;
    };

private:
    struct cmp {
        using is_transparent = void;
        bool operator()(const run& a, const run& b) const {
            return a.l < b.l;
        }
        bool operator()(const run& a, const T& b) const {
            return a.l < b;
        }
        bool operator()(const T& a, const run& b) const {
            return a < b.l;
        }
    };

public:
    using iterator = typename std::set<run, cmp>::const_iterator;
    range_map() {
    }
    // p を含む run。無ければ end()
    iterator find(T p) const {
        auto it = runs.upper_bound(p);
        if (it == runs.begin()) return runs.end();
        it--;
        if (it->r <= p) return runs.end();
        return it;
    }
    bool contains(T p) const {
        return find(p) != runs.end();
    }
    void assign(T l, T r, S x) {
        assign(l, r, x, [](T, T, const S&) {}, [](T, T, const S&) {});
    }
    // f: できた run ごとに呼ぶ, g: 消えた run ごとに呼ぶ
    template <class F, class G>
    void assign(T l, T r, S x, const F& f, const G& g) {
        assert(l < r);
        {
            auto it = find(l);
            if (it != runs.end() && r <= it->r && it->x == x) return;
        }
        T nl = l, nr = r;
        std::optional<run> left, right;
        auto first = runs.upper_bound(l);
        if (first != runs.begin()) {
            auto p = std::prev(first);
            if (l < p->r) {
                first = p;
                if (p->l < l) {
                    if (p->x == x) {
                        nl = p->l;
                    } else {
                        left = run{p->l, l, p->x};
                    }
                }
            } else if (p->r == l && p->x == x) {
                first = p;
                nl = p->l;
            }
        }
        if (first != runs.end() && first != runs.begin() && first->l == l) {
            auto p = std::prev(first);
            if (p->r == l && p->x == x) {
                first = p;
                nl = p->l;
            }
        }
        auto last = runs.lower_bound(r);
        if (last != runs.begin()) {
            auto q = std::prev(last);
            if (r < q->r) {
                if (q->x == x) {
                    nr = q->r;
                } else {
                    right = run{r, q->r, q->x};
                }
            }
        }
        if (last != runs.end() && last->l == r && last->x == x) {
            nr = last->r;
            last++;
        }
        for (auto it = first; it != last;) {
            g(it->l, it->r, it->x);
            it = runs.erase(it);
        }
        if (left) {
            runs.insert(*left);
            f(left->l, left->r, left->x);
        }
        runs.insert({nl, nr, x});
        f(nl, nr, x);
        if (right) {
            runs.insert(*right);
            f(right->l, right->r, right->x);
        }
    }
    void erase(T l, T r) {
        erase(l, r, [](T, T, const S&) {}, [](T, T, const S&) {});
    }
    template <class F, class G>
    void erase(T l, T r, const F& f, const G& g) {
        assert(l < r);
        auto it = runs.upper_bound(l);
        if (it != runs.begin() && l < std::prev(it)->r) it--;
        while (it != runs.end() && it->l < r) {
            run cur = *it;
            g(cur.l, cur.r, cur.x);
            it = runs.erase(it);
            if (cur.l < l) {
                runs.insert({cur.l, l, cur.x});
                f(cur.l, l, cur.x);
            }
            if (r < cur.r) {
                runs.insert({r, cur.r, cur.x});
                f(r, cur.r, cur.x);
            }
        }
    }
    int size() const {
        return int(runs.size());
    }
    iterator begin() const {
        return runs.begin();
    }
    iterator end() const {
        return runs.end();
    }

private:
    std::set<run, cmp> runs;
};
#line 10 "test/unit/range_map.test.cpp"
void stress(std::mt19937& rng) {
    const int U = 1 + rng() % 30;
    const int K = 1 + rng() % 4;  // 値の種類
    const int NONE = -1;
    std::vector<int> a(U, NONE);
    range_map<int, int> mp;
    std::map<int, long long> cnt;  // コールバックで管理する値ごとの個数
    long long runs = 0;            // コールバックで管理する run の個数
    auto f = [&](int l, int r, const int& x) {
        cnt[x] += r - l;
        runs++;
    };
    auto g = [&](int l, int r, const int& x) {
        cnt[x] -= r - l;
        runs--;
    };
    for (int it = 0; it < 200; it++) {
        int l = rng() % U, r = rng() % U;
        if (l > r) std::swap(l, r);
        r++;
        if (rng() % 3) {
            int x = rng() % K;
            mp.assign(l, r, x, f, g);
            for (int i = l; i < r; i++) a[i] = x;
        } else {
            mp.erase(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = NONE;
        }
        // 値と contains
        for (int p = 0; p < U; p++) {
            auto fi = mp.find(p);
            assert(mp.contains(p) == (a[p] != NONE));
            if (a[p] != NONE) {
                assert(fi != mp.end() && fi->l <= p && p < fi->r && fi->x == a[p]);
            } else {
                assert(fi == mp.end());
            }
        }
        // run が正規形: 値のある極大な連続区間と一致
        int expect_runs = 0;
        for (int p = 0; p < U; p++) expect_runs += a[p] != NONE && (p == 0 || a[p] != a[p - 1]);
        assert(mp.size() == expect_runs);
        assert(runs == expect_runs);
        int prev_r = -1;
        std::optional<int> prev_x;
        for (auto [rl, rr, rx] : mp) {
            assert(rl < rr);
            assert(prev_r <= rl);
            if (prev_r == rl) assert(*prev_x != rx);
            for (int p = rl; p < rr; p++) assert(a[p] == rx);
            if (rl > 0) assert(a[rl - 1] != rx);
            if (rr < U) assert(a[rr] != rx);
            prev_r = rr;
            prev_x = rx;
        }
        // ヒストグラム
        std::map<int, long long> expect;
        for (int v : a) {
            if (v != NONE) expect[v]++;
        }
        for (auto [v, c] : cnt) assert(c == expect[v]);
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 300; trial++) stress(rng);
    std::cout << "Hello World" << std::endl;
    return 0;
}

Back to top page