This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A" #include <vector> #include <iostream> #include <cassert> using namespace std; #include "../../lib/10-segment-tree/SegmentTree.cpp" #include "../../lib/99-operator/monoid/MonoidRangeMinPointUpdate.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; SegmentTree<MonoidRangeMinPointUpdate<long long>> Seg(N); while(Q--){ long long q,a,b; cin >> q >> a >> b; if(q) cout << Seg.fold(a,b+1) << endl; else Seg.operate(a,b); } return 0; }
#line 1 "test/segment-tree/SegmentTree-rmq.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A" #include <vector> #include <iostream> #include <cassert> using namespace std; #line 1 "lib/10-segment-tree/SegmentTree.cpp" /* * @title SegmentTree - 非再帰抽象化セグメント木 * @docs md/segment-tree/SegmentTree.md */ template<class Monoid> class SegmentTree { using TypeNode = typename Monoid::TypeNode; size_t length; size_t num; vector<TypeNode> node; vector<pair<int,int>> range; inline void build() { for (int i = length - 1; i >= 0; --i) node[i] = Monoid::func_fold(node[(i<<1)+0],node[(i<<1)+1]); range.resize(2 * length); for (int i = 0; i < length; ++i) range[i+length] = make_pair(i,i+1); for (int i = length - 1; i >= 0; --i) range[i] = make_pair(range[(i<<1)+0].first,range[(i<<1)+1].second); } public: //unitで初期化 SegmentTree(const size_t num): num(num) { for (length = 1; length <= num; length *= 2); node.resize(2 * length, Monoid::unit_node); build(); } //vectorで初期化 SegmentTree(const vector<TypeNode> & vec) : num(vec.size()) { for (length = 1; length <= vec.size(); length *= 2); node.resize(2 * length, Monoid::unit_node); for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i]; build(); } //同じinitで初期化 SegmentTree(const size_t num, const TypeNode init) : num(num) { for (length = 1; length <= num; length *= 2); node.resize(2 * length, Monoid::unit_node); for (int i = 0; i < length; ++i) node[i+length] = init; build(); } //[idx,idx+1) void operate(size_t idx, const TypeNode var) { if(idx < 0 || length <= idx) return; idx += length; node[idx] = Monoid::func_operate(node[idx],var); while(idx >>= 1) node[idx] = Monoid::func_fold(node[(idx<<1)+0],node[(idx<<1)+1]); } //[l,r) TypeNode fold(int l, int r) { if (l < 0 || length <= l || r < 0 || length < r) return Monoid::unit_node; TypeNode vl = Monoid::unit_node, vr = Monoid::unit_node; for(l += length, r += length; l < r; l >>=1, r >>=1) { if(l&1) vl = Monoid::func_fold(vl,node[l++]); if(r&1) vr = Monoid::func_fold(node[--r],vr); } return Monoid::func_fold(vl,vr); } //range[l,r) return [l,r] search max right int prefix_binary_search(int l, int r, TypeNode var) { assert(0 <= l && l < length && 0 < r && r <= length); TypeNode ret = Monoid::unit_node; size_t off = l; for(size_t idx = l+length; idx < 2*length && off < r; ){ if(range[idx].second<=r && !Monoid::func_check(Monoid::func_fold(ret,node[idx]),var)) { ret = Monoid::func_fold(ret,node[idx]); off = range[idx++].second; if(!(idx&1)) idx >>= 1; } else{ idx <<=1; } } return off; } //range(l,r] return [l,r] search max left int suffix_binary_search(const int l, const int r, const TypeNode var) { assert(-1 <= l && l < (int)length-1 && 0 <= r && r < length); TypeNode ret = Monoid::unit_node; int off = r; for(size_t idx = r+length; idx < 2*length && l < off; ){ if(l < range[idx].first && !Monoid::func_check(Monoid::func_fold(node[idx],ret),var)) { ret = Monoid::func_fold(node[idx],ret); off = range[idx--].first-1; if(idx&1) idx >>= 1; } else{ idx = (idx<<1)+1; } } return off; } void print(){ // cout << "node" << endl; // for(int i = 1,j = 1; i < 2*length; ++i) { // cout << node[i] << " "; // if(i==((1<<j)-1) && ++j) cout << endl; // } cout << "vector" << endl; cout << "{ " << fold(0,1); for(int i = 1; i < length; ++i) cout << ", " << fold(i,i+1); cout << " }" << endl; } }; #line 1 "lib/99-operator/monoid/MonoidRangeMinPointUpdate.cpp" /* * @title MonoidRangeMinPointUpdate - [区間min, 点更新] * @docs md/operator/monoid/MonoidRangeMinPointUpdate.md */ template<class T> struct MonoidRangeMinPointUpdate { using TypeNode = T; inline static constexpr TypeNode unit_node = (1LL<<31)-1; inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return min(l,r);} inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return r;} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var > nodeVal;} }; #line 9 "test/segment-tree/SegmentTree-rmq.test.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); int N,Q; cin >> N >> Q; SegmentTree<MonoidRangeMinPointUpdate<long long>> Seg(N); while(Q--){ long long q,a,b; cin >> q >> a >> b; if(q) cout << Seg.fold(a,b+1) << endl; else Seg.operate(a,b); } return 0; }