ba4dea3538 2012-01-22 kinaba: //------------------------------------------------------------- ba4dea3538 2012-01-22 kinaba: // Segment tree ba4dea3538 2012-01-22 kinaba: // in some general form ba4dea3538 2012-01-22 kinaba: // ba4dea3538 2012-01-22 kinaba: // Verified by 94afd8e13c 2013-09-14 kinaba: // - Codeforces 200 D 94afd8e13c 2013-09-14 kinaba: // - Codeforces 107 C (old version) 94afd8e13c 2013-09-14 kinaba: // - Codeforces 104 E (old version) ba4dea3538 2012-01-22 kinaba: //------------------------------------------------------------- ba4dea3538 2012-01-22 kinaba: ba4dea3538 2012-01-22 kinaba: class SegmentTree ba4dea3538 2012-01-22 kinaba: { 94afd8e13c 2013-09-14 kinaba: struct Node 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: int sum; 94afd8e13c 2013-09-14 kinaba: 94afd8e13c 2013-09-14 kinaba: static Node Zero() 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: Node c = {0}; 94afd8e13c 2013-09-14 kinaba: return c; 94afd8e13c 2013-09-14 kinaba: } 94afd8e13c 2013-09-14 kinaba: static Node One(int v) 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: Node c = {v}; 94afd8e13c 2013-09-14 kinaba: return c; 94afd8e13c 2013-09-14 kinaba: } 94afd8e13c 2013-09-14 kinaba: static Node Concat(const Node& l, const Node& r) 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: Node c = {l.sum + r.sum}; 94afd8e13c 2013-09-14 kinaba: return c; 94afd8e13c 2013-09-14 kinaba: } 94afd8e13c 2013-09-14 kinaba: static Node Repeat(const Node& n, int k) 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: Node c = {n.sum * k}; 94afd8e13c 2013-09-14 kinaba: return c; 94afd8e13c 2013-09-14 kinaba: } 94afd8e13c 2013-09-14 kinaba: 94afd8e13c 2013-09-14 kinaba: bool lazy; 94afd8e13c 2013-09-14 kinaba: }; 94afd8e13c 2013-09-14 kinaba: ba4dea3538 2012-01-22 kinaba: public: 58f56e668e 2012-02-18 kinaba: template<typename Seq> 58f56e668e 2012-02-18 kinaba: SegmentTree(const Seq& s) { ba4dea3538 2012-01-22 kinaba: int N = 1; ba4dea3538 2012-01-22 kinaba: while( N < s.size() ) ba4dea3538 2012-01-22 kinaba: N <<= 1; ba4dea3538 2012-01-22 kinaba: ba4dea3538 2012-01-22 kinaba: tree.resize(tree.size()+1); tree.back().resize(N); ba4dea3538 2012-01-22 kinaba: for(int i=0; i<N; ++i) 58f56e668e 2012-02-18 kinaba: tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero(); ba4dea3538 2012-01-22 kinaba: 58f56e668e 2012-02-18 kinaba: while(N>>=1) { ba4dea3538 2012-01-22 kinaba: tree.resize(tree.size()+1); tree.back().resize(N); ba4dea3538 2012-01-22 kinaba: for(int i=0; i<N; ++i) 58f56e668e 2012-02-18 kinaba: CalcMidNode(tree.size()-1, i); ba4dea3538 2012-01-22 kinaba: } ba4dea3538 2012-01-22 kinaba: } ba4dea3538 2012-01-22 kinaba: 34dd53bac9 2012-06-07 kinaba: Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) 58f56e668e 2012-02-18 kinaba: return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 58f56e668e 2012-02-18 kinaba: } 58f56e668e 2012-02-18 kinaba: 58f56e668e 2012-02-18 kinaba: template<typename Value> 94afd8e13c 2013-09-14 kinaba: void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n) 58f56e668e 2012-02-18 kinaba: SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); ba4dea3538 2012-01-22 kinaba: } ba4dea3538 2012-01-22 kinaba: 58f56e668e 2012-02-18 kinaba: private: 58f56e668e 2012-02-18 kinaba: Node QueryRec(int s, int e, int lv, int idx, int stride) ba4dea3538 2012-01-22 kinaba: { 58f56e668e 2012-02-18 kinaba: const int myL = stride*idx; 58f56e668e 2012-02-18 kinaba: const int myR = stride*(idx+1); 58f56e668e 2012-02-18 kinaba: if( e<=myL || myR<=s ) 58f56e668e 2012-02-18 kinaba: return Node::Zero(); 94afd8e13c 2013-09-14 kinaba: ResolveLazy(lv, idx); 94afd8e13c 2013-09-14 kinaba: 58f56e668e 2012-02-18 kinaba: if( s<=myL && myR<=e ) 58f56e668e 2012-02-18 kinaba: return tree[lv][idx]; 58f56e668e 2012-02-18 kinaba: return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2), 58f56e668e 2012-02-18 kinaba: QueryRec(s,e,lv-1,idx*2+1,stride/2)); ba4dea3538 2012-01-22 kinaba: } ba4dea3538 2012-01-22 kinaba: 58f56e668e 2012-02-18 kinaba: void SetRec(int s, int e, const Node& n, int lv, int idx, int stride) ba4dea3538 2012-01-22 kinaba: { 58f56e668e 2012-02-18 kinaba: const int myL = stride*idx; 58f56e668e 2012-02-18 kinaba: const int myR = stride*(idx+1); 58f56e668e 2012-02-18 kinaba: if( e<=myL || myR<=s ) ba4dea3538 2012-01-22 kinaba: return; 94afd8e13c 2013-09-14 kinaba: ResolveLazy(lv, idx); 94afd8e13c 2013-09-14 kinaba: 58f56e668e 2012-02-18 kinaba: if( stride == 1 ) { 58f56e668e 2012-02-18 kinaba: tree[lv][idx] = n; 58f56e668e 2012-02-18 kinaba: } else { 94afd8e13c 2013-09-14 kinaba: if( s<=myL && myR<=e ) { 94afd8e13c 2013-09-14 kinaba: tree[lv][idx] = n; 94afd8e13c 2013-09-14 kinaba: tree[lv][idx].lazy = true; 94afd8e13c 2013-09-14 kinaba: ResolveLazy(lv, idx); 94afd8e13c 2013-09-14 kinaba: return; 94afd8e13c 2013-09-14 kinaba: } 58f56e668e 2012-02-18 kinaba: SetRec(s,e,n,lv-1,idx*2,stride/2); 58f56e668e 2012-02-18 kinaba: SetRec(s,e,n,lv-1,idx*2+1,stride/2); 58f56e668e 2012-02-18 kinaba: CalcMidNode(lv, idx); ba4dea3538 2012-01-22 kinaba: } 58f56e668e 2012-02-18 kinaba: } 58f56e668e 2012-02-18 kinaba: 94afd8e13c 2013-09-14 kinaba: void CalcMidNode(int lv, int idx) 94afd8e13c 2013-09-14 kinaba: { 94afd8e13c 2013-09-14 kinaba: tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]); 94afd8e13c 2013-09-14 kinaba: } ba4dea3538 2012-01-22 kinaba: 94afd8e13c 2013-09-14 kinaba: void ResolveLazy(int lv, int idx) 58f56e668e 2012-02-18 kinaba: { 94afd8e13c 2013-09-14 kinaba: if(tree[lv][idx].lazy) { 94afd8e13c 2013-09-14 kinaba: if(lv > 0) { 94afd8e13c 2013-09-14 kinaba: tree[lv-1][idx*2] = tree[lv][idx]; 94afd8e13c 2013-09-14 kinaba: tree[lv-1][idx*2+1] = tree[lv][idx]; 94afd8e13c 2013-09-14 kinaba: } 94afd8e13c 2013-09-14 kinaba: tree[lv][idx] = Node::Repeat(tree[lv][idx], 1<<lv); 94afd8e13c 2013-09-14 kinaba: } ba4dea3538 2012-01-22 kinaba: } 58f56e668e 2012-02-18 kinaba: 58f56e668e 2012-02-18 kinaba: vector< vector<Node> > tree; ba4dea3538 2012-01-22 kinaba: };