Fu_L's Library

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

View the Project on GitHub Fu-L/cp-library

:heavy_check_mark: verify/unit_test/data_structure/segment_set.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/random/permuted_congruential_generator.hpp"
#include "../../../src/data_structure/segment_set.hpp"
vector<pair<int, int>> enumerate_segments(const vector<bool>& used) {
    vector<pair<int, int>> res;
    const int n = used.size();
    int i = 0;
    while(i < n) {
        if(!used[i]) {
            ++i;
            continue;
        }
        int j = i;
        while(j < n and used[j]) ++j;
        res.emplace_back(i, j);
        i = j;
    }
    return res;
}
void assert_same(const SegmentSet<int>& st, const vector<bool>& used) {
    const vector<pair<int, int>> expected = enumerate_segments(used);
    assert(st.size() == expected.size());
    vector<pair<int, int>> actual;
    for(const auto& p : st) actual.push_back(p);
    assert(actual == expected);
    const int n = used.size();
    rep(x, 0, n) {
        const auto it = st.find(x);
        if(used[x]) {
            assert(it != st.end());
            assert(it->first <= x and x < it->second);
        } else {
            assert(it == st.end());
        }
        int expected_next = numeric_limits<int>::max();
        rep(y, x, n) {
            if(used[y]) {
                expected_next = y;
                break;
            }
        }
        assert(st.next(x) == expected_next);
        const auto lb = st.lower_bound(x);
        pair<int, int> expected_lb{-1, -1};
        for(const auto& p : expected) {
            if(p.second <= x) continue;
            expected_lb = p;
            break;
        }
        if(expected_lb.first == -1) {
            assert(lb == st.end());
        } else {
            assert(lb != st.end());
            assert(lb->first == expected_lb.first);
            assert(lb->second == expected_lb.second);
        }
    }
}
void test_sample_like() {
    SegmentSet<int> st;
    vector<bool> used(25);
    auto insert = [&](int l, int r) {
        st.insert(l, r);
        rep(i, l, r) used[i] = true;
        assert_same(st, used);
    };
    auto erase = [&](int l, int r) {
        st.erase(l, r);
        rep(i, l, r) used[i] = false;
        assert_same(st, used);
    };
    insert(3, 7);
    insert(10, 15);
    insert(13, 20);
    erase(5, 13);
    insert(7, 7);
    erase(13, 13);
}
void test_random() {
    constexpr int n = 80;
    SegmentSet<int> st;
    vector<bool> used(n);
    const int query_num = 1000;
    rep(_, 0, query_num) {
        int l = rng(0, n - 1);
        int r = rng(l, n);
        if(rng(0, 1)) {
            st.insert(l, r);
            rep(i, l, r) used[i] = true;
        } else {
            st.erase(l, r);
            rep(i, l, r) used[i] = false;
        }
        assert_same(st, used);
    }
}
int main(void) {
    test_sample_like();
    constexpr int test_num = 100;
    rep(_, 0, test_num) {
        test_random();
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
#line 1 "verify/unit_test/data_structure/segment_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/random/permuted_congruential_generator.hpp"
struct PermutedCongruentialGenerator {
    template <typename T>
        requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
    inline T operator()(const T l, const T r) {
        assert(l <= r);
        if constexpr(is_integral_v<T>) {
            const unsigned int x = next32();
            if constexpr(is_signed_v<T>) {
                const uint64_t range = uint64_t(int64_t(r) - int64_t(l)) + 1;
                const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
                return T(int64_t(l) + int64_t(offset));
            } else {
                const uint64_t range = uint64_t(r) - uint64_t(l) + 1;
                const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
                return T(l + T(offset));
            }
        } else {
            static constexpr unsigned long long denom = 1ull << 53;
            const unsigned long long x = next64() >> 11;
            const double u = static_cast<double>(x) / denom;
            return l + (r - l) * u;
        }
    }

   private:
    static constexpr unsigned long long MULT = 6364136223846793005;
    static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
    inline unsigned int next32() {
        unsigned long long x = state;
        state *= MULT;
        const unsigned int count = x >> 61;
        x ^= x >> 22;
        return static_cast<unsigned int>(x >> (22 + count));
    }
    inline unsigned long long next64() {
        return (static_cast<unsigned long long>(next32()) << 32) | next32();
    }
} rng;
#line 3 "src/data_structure/segment_set.hpp"
template <typename T>
struct SegmentSet {
    SegmentSet() = default;
    using const_iterator = typename map<T, T>::const_iterator;
    const_iterator begin() const {
        return st.begin();
    }
    const_iterator end() const {
        return st.end();
    }
    const_iterator find(const T& x) const {
        auto it = st.upper_bound(x);
        if(it == st.begin() or (--it)->second <= x) return st.end();
        return it;
    }
    const_iterator lower_bound(const T& x) const {
        auto it = st.lower_bound(x);
        if(it == st.begin() or prev(it)->second <= x) return it;
        return prev(it);
    }
    void insert(T l, T r) {
        assert(l <= r);
        if(l == r) return;
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L != R) {
            l = min(l, L->first);
            r = max(r, prev(R)->second);
            st.erase(L, R);
        }
        st[l] = r;
    }
    void erase(const T& l, const T& r) {
        assert(l <= r);
        if(l == r) return;
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L == R) return;
        const T nl = min(l, L->first), nr = max(r, prev(R)->second);
        st.erase(L, R);
        if(nl < l) st[nl] = l;
        if(r < nr) st[r] = nr;
    }
    T next(const T& x) const {
        auto it = this->lower_bound(x);
        if(it == this->end()) return numeric_limits<T>::max();
        return max<T>(x, it->first);
    }
    size_t size() const {
        return st.size();
    }

   private:
    map<T, T> st;
};
#line 5 "verify/unit_test/data_structure/segment_set.test.cpp"
vector<pair<int, int>> enumerate_segments(const vector<bool>& used) {
    vector<pair<int, int>> res;
    const int n = used.size();
    int i = 0;
    while(i < n) {
        if(!used[i]) {
            ++i;
            continue;
        }
        int j = i;
        while(j < n and used[j]) ++j;
        res.emplace_back(i, j);
        i = j;
    }
    return res;
}
void assert_same(const SegmentSet<int>& st, const vector<bool>& used) {
    const vector<pair<int, int>> expected = enumerate_segments(used);
    assert(st.size() == expected.size());
    vector<pair<int, int>> actual;
    for(const auto& p : st) actual.push_back(p);
    assert(actual == expected);
    const int n = used.size();
    rep(x, 0, n) {
        const auto it = st.find(x);
        if(used[x]) {
            assert(it != st.end());
            assert(it->first <= x and x < it->second);
        } else {
            assert(it == st.end());
        }
        int expected_next = numeric_limits<int>::max();
        rep(y, x, n) {
            if(used[y]) {
                expected_next = y;
                break;
            }
        }
        assert(st.next(x) == expected_next);
        const auto lb = st.lower_bound(x);
        pair<int, int> expected_lb{-1, -1};
        for(const auto& p : expected) {
            if(p.second <= x) continue;
            expected_lb = p;
            break;
        }
        if(expected_lb.first == -1) {
            assert(lb == st.end());
        } else {
            assert(lb != st.end());
            assert(lb->first == expected_lb.first);
            assert(lb->second == expected_lb.second);
        }
    }
}
void test_sample_like() {
    SegmentSet<int> st;
    vector<bool> used(25);
    auto insert = [&](int l, int r) {
        st.insert(l, r);
        rep(i, l, r) used[i] = true;
        assert_same(st, used);
    };
    auto erase = [&](int l, int r) {
        st.erase(l, r);
        rep(i, l, r) used[i] = false;
        assert_same(st, used);
    };
    insert(3, 7);
    insert(10, 15);
    insert(13, 20);
    erase(5, 13);
    insert(7, 7);
    erase(13, 13);
}
void test_random() {
    constexpr int n = 80;
    SegmentSet<int> st;
    vector<bool> used(n);
    const int query_num = 1000;
    rep(_, 0, query_num) {
        int l = rng(0, n - 1);
        int r = rng(l, n);
        if(rng(0, 1)) {
            st.insert(l, r);
            rep(i, l, r) used[i] = true;
        } else {
            st.erase(l, r);
            rep(i, l, r) used[i] = false;
        }
        assert_same(st, used);
    }
}
int main(void) {
    test_sample_like();
    constexpr int test_num = 100;
    rep(_, 0, test_num) {
        test_random();
    }
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
}
Back to top page