test/unit/dual_segtree.test.cpp

• View this file on GitHub
• Last update: 2026-05-18 10:25:36+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• Dual Segment Tree (datastructure/dual_segtree.hpp)

Code

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

#include "datastructure/dual_segtree.hpp"
using F = std::pair<long long, long long>;
F composition(F f, F g) {
    return {f.first * g.first, f.first * g.second + f.second};
}
F id() {
    return {1, 0};
}
template <bool is_commutative>
void stress(std::mt19937 &rng) {
    const int N = 30;
    const int Q = 2000;
    dual_segtree<F, composition, id, is_commutative> seg(N);
    std::vector<F> naive(N, id());
    auto gen = [&]() -> F {
        if constexpr (is_commutative) {
            return {1, (long long)(rng() % 10)};
        } else {
            return {(long long)(rng() % 5), (long long)(rng() % 5)};
        }
    };
    for (int q = 0; q < Q; q++) {
        int t = rng() % 3;
        if (t == 0) {
            int l = rng() % N;
            int r = l + 1 + rng() % (N - l);
            F f = gen();
            seg.apply(l, r, f);
            for (int i = l; i < r; i++) naive[i] = composition(f, naive[i]);
        } else if (t == 1) {
            int p = rng() % N;
            F v = gen();
            seg.set(p, v);
            naive[p] = v;
        } else {
            int p = rng() % N;
            assert(seg.get(p) == naive[p]);
        }
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 20; trial++) {
        stress<false>(rng);
        stress<true>(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}

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

#line 2 "datastructure/dual_segtree.hpp"
template <class F, F (*composition)(F, F), F (*id)(), bool is_commutative = false>
struct dual_segtree {
public:
    dual_segtree() {
    }
    dual_segtree(int n) {
        size = 1;
        height = 0;
        while (size < n) size <<= 1, height++;
        lz.assign(2 * size, id());
    }
    void set(int p, const F &x) {
        p += size;
        thrust(p);
        lz[p] = x;
    }
    void apply(int l, int r, const F &f) {
        l += size;
        r += size - 1;
        if constexpr (!is_commutative) {
            thrust(l);
            thrust(r);
        }
        r++;
        while (l < r) {
            if (l & 1) lz[l] = composition(f, lz[l]), ++l;
            if (r & 1) --r, lz[r] = composition(f, lz[r]);
            l >>= 1, r >>= 1;
        }
    }
    F get(int p) {
        if constexpr (is_commutative) {
            F ret = id();
            p += size;
            while (p > 0) {
                ret = composition(lz[p], ret);
                p >>= 1;
            }
            return ret;
        } else {
            thrust(p += size);
            return lz[p];
        }
    }

private:
    int size, height;
    std::vector<F> lz;
    inline void propagate(int k) {
        lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]);
        lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]);
        lz[k] = id();
    }
    inline void thrust(int k) {
        for (int i = height; i > 0; i--) propagate(k >> i);
    }
};
#line 9 "test/unit/dual_segtree.test.cpp"
using F = std::pair<long long, long long>;
F composition(F f, F g) {
    return {f.first * g.first, f.first * g.second + f.second};
}
F id() {
    return {1, 0};
}
template <bool is_commutative>
void stress(std::mt19937 &rng) {
    const int N = 30;
    const int Q = 2000;
    dual_segtree<F, composition, id, is_commutative> seg(N);
    std::vector<F> naive(N, id());
    auto gen = [&]() -> F {
        if constexpr (is_commutative) {
            return {1, (long long)(rng() % 10)};
        } else {
            return {(long long)(rng() % 5), (long long)(rng() % 5)};
        }
    };
    for (int q = 0; q < Q; q++) {
        int t = rng() % 3;
        if (t == 0) {
            int l = rng() % N;
            int r = l + 1 + rng() % (N - l);
            F f = gen();
            seg.apply(l, r, f);
            for (int i = l; i < r; i++) naive[i] = composition(f, naive[i]);
        } else if (t == 1) {
            int p = rng() % N;
            F v = gen();
            seg.set(p, v);
            naive[p] = v;
        } else {
            int p = rng() % N;
            assert(seg.get(p) == naive[p]);
        }
    }
}
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 20; trial++) {
        stress<false>(rng);
        stress<true>(rng);
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}

Back to top page