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: 			if(k==0) return Zero();
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: };