This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D" #include <iostream> #include "C++/ds/DualSegmentTree.hpp" int main() { int n, q; std::cin >> n >> q; DualSegTree<int> seg(n, [](const int a, const int b) -> int { return b; }, INT32_MAX); while(q--) { int h; std::cin >> h; if(h == 0) { int s, t, x; std::cin >> s >> t >> x; seg.apply(s, ++t, x); } else { int i; std::cin >> i; std::cout << seg[i] << '\n'; } } }
#line 1 "test/dualsegtree.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D" #include <iostream> #line 2 "C++/ds/DualSegmentTree.hpp" #pragma GCC diagnostic ignored "-Wreorder" #include <vector> #include <functional> template <class T> struct DualSegTree { private: using F = std::function<T(T, T)>; int sz, h; std::vector<T> lazy; const T id; const F ap; inline void propagate(const int k) { if(lazy[k] != id) { lazy[2 * k] = ap(lazy[2 * k], lazy[k]); lazy[2 * k + 1] = ap(lazy[2 * k + 1], lazy[k]); lazy[k] = id; } } inline void thrust(const int k) { for(int i = h; i > 0; i--) { propagate(k >> i); } } public: DualSegTree(const int n, const F &ap, const T &id): ap(ap), id(id) { sz = 1; h = 0; while(sz < n) { sz <<= 1; h++; } lazy.assign(2 * sz, id); } void apply(int a, int b, const T &x) { thrust(a += sz); thrust(b += sz - 1); for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if(l & 1) { lazy[l] = ap(lazy[l], x); l++; } if(r & 1) { r--; lazy[r] = ap(lazy[r], x); } } } inline T operator[](int k) { thrust(k += sz); return lazy[k]; } }; /** * @brief 双対セグ木 * @see https://ei1333.github.io/library/structure/segment-tree/dual-segment-tree.hpp */ #line 4 "test/dualsegtree.test.cpp" int main() { int n, q; std::cin >> n >> q; DualSegTree<int> seg(n, [](const int a, const int b) -> int { return b; }, INT32_MAX); while(q--) { int h; std::cin >> h; if(h == 0) { int s, t, x; std::cin >> s >> t >> x; seg.apply(s, ++t, x); } else { int i; std::cin >> i; std::cout << seg[i] << '\n'; } } }