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_A" #include <iostream> #include <limits> #include "C++/ds/SegmentTree.hpp" int main() { int n, q; std::cin >> n >> q; SegTree<int> seg(n, [](const int x, const int y) -> int { return std::min(x, y); }, std::numeric_limits<int>::max()); while(q--) { int com, x, y; std::cin >> com >> x >> y; if(com == 0) { seg.update(x, y); } else { std::cout << seg.query(x, y + 1) << '\n'; } } }
#line 1 "test/segtree2.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A" #include <iostream> #include <limits> #line 2 "C++/ds/SegmentTree.hpp" #pragma GCC diagnostic ignored "-Wreorder" #include <vector> #include <functional> template <class T> struct SegTree { private: using F = std::function<T(T, T)>; int n, rank, fine; const F f; const T e; std::vector<T> dat; public: SegTree(const int n_, const F f_, const T& e_): f(f_), e(e_), fine(n_) { n=1,rank=0; while(fine>n) n<<=1LL,rank++; dat.assign(2*n,e_); } SegTree(const std::vector<T> &v, const F f_, const T e_): f(f_), e(e_), fine(v.size()) { n=1,rank=0; while(fine>n) n<<=1LL,rank++; dat.assign(2*n,e_); for(size_t i=0; i<v.size(); ++i) update(i,v[i]); } T operator[](int i) const { return dat[i+n]; } void update(int i, const T& x) { i+=n; dat[i]=x; while(i>>=1LL) dat[i]=f(dat[2*i],dat[2*i+1]); } void add(int i, const T& x) { i+=n; dat[i]+=x; while(i>>=1LL) dat[i]=f(dat[2*i],dat[2*i+1]); } T query(int a, int b) const { T l=e,r=e; for(a+=n, b+=n; a<b; a>>=1LL,b>>=1LL) { if(a&1) l=f(l,dat[a++]); if(b&1) r=f(dat[--b],r); } return f(l,r); } T alle() const { return dat[1]; } template <class Boolean=bool> inline int find_left(int r, const Boolean &fn) { if(!r) return 0; int h=0,i=r+n; T val=e; for(; h <= rank; h++) if(i>>h&1){ T val2=f(val,dat[i>>h^1]); if(fn(val2)){ i -= 1<<h; if(i==n) return 0; val=val2; } else break; } for(; h--;){ T val2 = f(val,dat[(i>>h)-1]); if(fn(val2)){ i-=1<<h; if(i==n) return 0; val=val2; } } return i-n; } template <class Boolean=bool> inline int find_right(int l, const Boolean &fn) { if(l==fine) return fine; int h=0,i=l+n; T val=e; for(; h<=rank; h++) if(i>>h&1){ T val2=f(val,dat[i>>h]); if(fn(val2)){ i+=1LL<<h; if(i==n*2) return fine; val=val2; } else break; } for(; h--;){ T val2=f(val, dat[i>>h]); if(fn(val2)){ i+=1LL<<h; if(i==n*2) return fine; val=val2; } } return std::min(i-n,fine); } }; /** * @brief セグメント木 * @see https://github.com/tatyam-prime/kyopro_library/blob/master/SegmentTree.cpp */ #line 5 "test/segtree2.test.cpp" int main() { int n, q; std::cin >> n >> q; SegTree<int> seg(n, [](const int x, const int y) -> int { return std::min(x, y); }, std::numeric_limits<int>::max()); while(q--) { int com, x, y; std::cin >> com >> x >> y; if(com == 0) { seg.update(x, y); } else { std::cout << seg.query(x, y + 1) << '\n'; } } }