test/unit/range_set.test.cpp

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

Depends on

• Range Set (datastructure/range_set.hpp)

Code

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

#include "datastructure/range_set.hpp"
void stress(std::mt19937& rng) {
    const int U = 1 + rng() % 30;
    std::vector<bool> a(U, false);
    range_set<int> st;
    long long len = 0;  // コールバックで管理する被覆長
    auto f = [&](int l, int r) { len += r - l; };
    auto g = [&](int l, int r) { len -= r - l; };
    for (int it = 0; it < 200; it++) {
        int l = rng() % U, r = rng() % U;
        if (l > r) std::swap(l, r);
        r++;
        if (rng() % 2) {
            st.insert(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = true;
        } else {
            st.erase(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = false;
        }
        // contains, mex
        long long naive_len = 0;
        for (int p = 0; p < U; p++) {
            assert(st.contains(p) == a[p]);
            naive_len += a[p];
            int m = p;
            while (m < U && a[m]) m++;
            assert(st.mex(p) == m);
        }
        assert(len == naive_len);
        // size: 極大な連続区間の個数
        int runs = 0;
        for (int p = 0; p < U; p++) runs += a[p] && (p == 0 || !a[p - 1]);
        assert(st.size() == runs);
        // 列挙: 昇順・互いに離れている・中身が一致
        int prev_r = -1;
        for (auto [x, y] : st) {
            assert(x < y);
            assert(prev_r < x);
            for (int p = x; p < y; p++) assert(a[p]);
            prev_r = y;
        }
        // covers, find
        int ql = rng() % U, qr = rng() % U;
        if (ql > qr) std::swap(ql, qr);
        qr++;
        bool cov = true;
        for (int p = ql; p < qr; p++) cov &= a[p];
        assert(st.covers(ql, qr) == cov);
        auto fi = st.find(ql);
        if (a[ql]) {
            assert(fi != st.end() && fi->first <= ql && ql < fi->second);
        } else {
            assert(fi == st.end());
        }
    }
}
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_set.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#line 3 "datastructure/range_set.hpp"
#include <map>
template <class T>
struct range_set {
public:
    using iterator = typename std::map<T, T>::const_iterator;
    range_set() {
    }
    // p を含む区間。無ければ end()
    iterator find(T p) const {
        auto it = ranges.upper_bound(p);
        if (it == ranges.begin()) return ranges.end();
        it--;
        if (it->second <= p) return ranges.end();
        return it;
    }
    bool contains(T p) const {
        return find(p) != ranges.end();
    }
    // [l, r) が 1 つの区間に含まれるか
    bool covers(T l, T r) const {
        assert(l < r);
        auto it = find(l);
        return it != ranges.end() && r <= it->second;
    }
    // x 以上で含まれない最小の値（整数向け）
    T mex(T x) const {
        auto it = find(x);
        return it == ranges.end() ? x : it->second;
    }
    void insert(T l, T r) {
        insert(l, r, [](T, T) {}, [](T, T) {});
    }
    // f: 追加された区間ごとに呼ぶ, g: 削除された区間ごとに呼ぶ
    template <class F, class G>
    void insert(T l, T r, const F& f, const G& g) {
        assert(l < r);
        auto it = ranges.upper_bound(l);
        if (it != ranges.begin() && l <= std::prev(it)->second) it--;
        while (it != ranges.end() && it->first <= r) {
            l = std::min(l, it->first);
            r = std::max(r, it->second);
            g(it->first, it->second);
            it = ranges.erase(it);
        }
        ranges[l] = r;
        f(l, r);
    }
    void erase(T l, T r) {
        erase(l, r, [](T, T) {}, [](T, T) {});
    }
    template <class F, class G>
    void erase(T l, T r, const F& f, const G& g) {
        assert(l < r);
        auto it = ranges.upper_bound(l);
        if (it != ranges.begin() && l < std::prev(it)->second) it--;
        while (it != ranges.end() && it->first < r) {
            T a = it->first, b = it->second;
            g(a, b);
            it = ranges.erase(it);
            if (a < l) {
                ranges[a] = l;
                f(a, l);
            }
            if (r < b) {
                ranges[r] = b;
                f(r, b);
            }
        }
    }
    int size() const {
        return int(ranges.size());
    }
    iterator begin() const {
        return ranges.begin();
    }
    iterator end() const {
        return ranges.end();
    }

private:
    std::map<T, T> ranges;
};
#line 8 "test/unit/range_set.test.cpp"
void stress(std::mt19937& rng) {
    const int U = 1 + rng() % 30;
    std::vector<bool> a(U, false);
    range_set<int> st;
    long long len = 0;  // コールバックで管理する被覆長
    auto f = [&](int l, int r) { len += r - l; };
    auto g = [&](int l, int r) { len -= r - l; };
    for (int it = 0; it < 200; it++) {
        int l = rng() % U, r = rng() % U;
        if (l > r) std::swap(l, r);
        r++;
        if (rng() % 2) {
            st.insert(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = true;
        } else {
            st.erase(l, r, f, g);
            for (int i = l; i < r; i++) a[i] = false;
        }
        // contains, mex
        long long naive_len = 0;
        for (int p = 0; p < U; p++) {
            assert(st.contains(p) == a[p]);
            naive_len += a[p];
            int m = p;
            while (m < U && a[m]) m++;
            assert(st.mex(p) == m);
        }
        assert(len == naive_len);
        // size: 極大な連続区間の個数
        int runs = 0;
        for (int p = 0; p < U; p++) runs += a[p] && (p == 0 || !a[p - 1]);
        assert(st.size() == runs);
        // 列挙: 昇順・互いに離れている・中身が一致
        int prev_r = -1;
        for (auto [x, y] : st) {
            assert(x < y);
            assert(prev_r < x);
            for (int p = x; p < y; p++) assert(a[p]);
            prev_r = y;
        }
        // covers, find
        int ql = rng() % U, qr = rng() % U;
        if (ql > qr) std::swap(ql, qr);
        qr++;
        bool cov = true;
        for (int p = ql; p < qr; p++) cov &= a[p];
        assert(st.covers(ql, qr) == cov);
        auto fi = st.find(ql);
        if (a[ql]) {
            assert(fi != st.end() && fi->first <= ql && ql < fi->second);
        } else {
            assert(fi == st.end());
        }
    }
}
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