This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://yukicoder.me/problems/no/789" #include <vector> #include <iostream> #include <cassert> #include <stack> using namespace std; #include "../../lib/10-segment-tree/DynamicSegmentTree.cpp" #include "../../lib/99-operator/monoid/MonoidRangeSumPointAdd.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); DynamicSegmentTree<MonoidRangeSumPointAdd<long long>> seg; int N; cin >> N; long long ans = 0; while(N--) { int q,l,r; cin >> q >> l >> r; if(q==0) seg.operate(l,r); else ans += seg.fold(l,r+1); } cout << ans << endl; return 0; }
#line 1 "test/segment-tree/DynamicSegmentTree-rsq-2.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/789" #include <vector> #include <iostream> #include <cassert> #include <stack> using namespace std; #line 1 "lib/10-segment-tree/DynamicSegmentTree.cpp" /* * @title DynamicSegmentTree - 非再帰抽象化動的セグメント木 * @docs md/segment-tree/DynamicSegmentTree.md */ template<class Monoid> class DynamicSegmentTree { using TypeNode = typename Monoid::TypeNode; using i64 = long long; struct Node{ Node *left, *right; TypeNode val; Node():left(nullptr),right(nullptr),val(Monoid::unit_node) {} }; TypeNode dfs(i64 l,i64 r,i64 nl,i64 nr,Node* node) { if(l <= nl && nr <= r) return node->val; if(nr <= l || r <= nl) return Monoid::unit_node; TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node; i64 m = (nl+nr)>>1; if(node->left) vl = dfs(l,r,nl,m,node->left); if(node->right) vr = dfs(l,r,m,nr,node->right); return Monoid::func_fold(vl,vr); } i64 length; Node *root; public: //unitで初期化 DynamicSegmentTree() : length(1) { root = new Node(); } //[idx,idx+1) void operate(i64 idx, const TypeNode val) { if(idx < 0) return; for (;length <= idx; length *= 2) { Node *new_root = new Node(); TypeNode val = root->val; new_root->left = root; root = new_root; root->val = val; } Node* node = root; i64 l = 0, r = length, m; stack<Node*> st; while(r-l>1) { st.push(node); m = (r+l)>>1; if(idx<m) { r = m; if(!node->left) node->left=new Node(); node = node->left; } else { l = m; if(!node->right) node->right = new Node(); node = node->right; } } node->val = Monoid::func_operate(node->val,val); while(st.size()) { node = st.top(); st.pop(); TypeNode vl=Monoid::unit_node, vr=Monoid::unit_node; if(node->left) vl = node->left->val; if(node->right) vr = node->right->val; node->val = Monoid::func_fold(vl,vr); } } //[l,r) TypeNode fold(i64 l, i64 r) { if (l < 0 || length <= l || r < 0) return Monoid::unit_node; return dfs(l,r,0,length,root); } }; #line 1 "lib/99-operator/monoid/MonoidRangeSumPointAdd.cpp" /* * @title MonoidRangeSumPointAdd - [区間和, 一点加算] * @docs md/operator/monoid/MonoidRangeSumPointAdd.md */ template<class T> struct MonoidRangeSumPointAdd { using TypeNode = T; inline static constexpr TypeNode unit_node = 0; inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;} inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return l+r;} inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;} }; #line 10 "test/segment-tree/DynamicSegmentTree-rsq-2.test.cpp" int main(void){ cin.tie(0);ios::sync_with_stdio(false); DynamicSegmentTree<MonoidRangeSumPointAdd<long long>> seg; int N; cin >> N; long long ans = 0; while(N--) { int q,l,r; cin >> q >> l >> r; if(q==0) seg.operate(l,r); else ans += seg.fold(l,r+1); } cout << ans << endl; return 0; }