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
58f56e668e 2012-02-18        kinaba: //   - Codeforces 107 C
ba4dea3538 2012-01-22        kinaba: //   - Codeforces 104 E
ba4dea3538 2012-01-22        kinaba: //-------------------------------------------------------------
ba4dea3538 2012-01-22        kinaba: 
58f56e668e 2012-02-18        kinaba: template<typename Node>
58f56e668e 2012-02-18        kinaba: class SegmentTree
58f56e668e 2012-02-18        kinaba: {
58f56e668e 2012-02-18        kinaba: public:
58f56e668e 2012-02-18        kinaba: 	template<typename Seq>
58f56e668e 2012-02-18        kinaba: 	SegmentTree(const Seq& s) {
58f56e668e 2012-02-18        kinaba: 		int N = 1;
58f56e668e 2012-02-18        kinaba: 		while( N < s.size() )
58f56e668e 2012-02-18        kinaba: 			N <<= 1;
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: 		tree.resize(tree.size()+1); tree.back().resize(N);
58f56e668e 2012-02-18        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();
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: 		while(N>>=1) {
58f56e668e 2012-02-18        kinaba: 			tree.resize(tree.size()+1); tree.back().resize(N);
58f56e668e 2012-02-18        kinaba: 			for(int i=0; i<N; ++i)
58f56e668e 2012-02-18        kinaba: 				CalcMidNode(tree.size()-1, i);
58f56e668e 2012-02-18        kinaba: 		}
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        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>
34dd53bac9 2012-06-07        kinaba: 	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|)
58f56e668e 2012-02-18        kinaba: 		SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: private:
58f56e668e 2012-02-18        kinaba: 	void CalcMidNode(int lv, int idx)
58f56e668e 2012-02-18        kinaba: 	{
58f56e668e 2012-02-18        kinaba: 		tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: 	Node QueryRec(int s, int e, int lv, int idx, int stride)
58f56e668e 2012-02-18        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();
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));
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: 	void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
58f56e668e 2012-02-18        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;
58f56e668e 2012-02-18        kinaba: 		if( stride == 1 ) {
58f56e668e 2012-02-18        kinaba: 			tree[lv][idx] = n;
58f56e668e 2012-02-18        kinaba: 		} else {
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);
58f56e668e 2012-02-18        kinaba: 		}
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: 	vector< vector<Node> > tree;
58f56e668e 2012-02-18        kinaba: };
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: struct Node
58f56e668e 2012-02-18        kinaba: {
58f56e668e 2012-02-18        kinaba: 	double sum;
58f56e668e 2012-02-18        kinaba: 	double maxLeft;
58f56e668e 2012-02-18        kinaba: 	double maxRight;
58f56e668e 2012-02-18        kinaba: 	double maxSum;
58f56e668e 2012-02-18        kinaba: 	static Node Zero()
58f56e668e 2012-02-18        kinaba: 	{
58f56e668e 2012-02-18        kinaba: 		Node c = {0, 0, 0, 0};
58f56e668e 2012-02-18        kinaba: 		return c;
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 	static Node One(double v)
58f56e668e 2012-02-18        kinaba: 	{
58f56e668e 2012-02-18        kinaba: 		Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
58f56e668e 2012-02-18        kinaba: 		return c;
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: 	static Node Concat(const Node& l, const Node& r)
58f56e668e 2012-02-18        kinaba: 	{
58f56e668e 2012-02-18        kinaba: 		Node c = {
58f56e668e 2012-02-18        kinaba: 			l.sum + r.sum,
58f56e668e 2012-02-18        kinaba: 			max(l.maxLeft, l.sum+r.maxLeft),
58f56e668e 2012-02-18        kinaba: 			max(l.maxRight+r.sum, r.maxRight),
58f56e668e 2012-02-18        kinaba: 			max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
58f56e668e 2012-02-18        kinaba: 		};
58f56e668e 2012-02-18        kinaba: 		return c;
58f56e668e 2012-02-18        kinaba: 	}
58f56e668e 2012-02-18        kinaba: };
58f56e668e 2012-02-18        kinaba: 
58f56e668e 2012-02-18        kinaba: /*
ba4dea3538 2012-01-22        kinaba: class SegmentTree
ba4dea3538 2012-01-22        kinaba: {
ba4dea3538 2012-01-22        kinaba: 	// --- DATA FOR EACH NODE ---
ba4dea3538 2012-01-22        kinaba: 	struct Node
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		int sum;
ba4dea3538 2012-01-22        kinaba: 		int maxLeft;
ba4dea3538 2012-01-22        kinaba: 		int minLeft;
ba4dea3538 2012-01-22        kinaba: 		int n4;
ba4dea3538 2012-01-22        kinaba: 		int n7;
ba4dea3538 2012-01-22        kinaba: 		bool switched;
ba4dea3538 2012-01-22        kinaba: 	};
ba4dea3538 2012-01-22        kinaba: 	// --- DATA FOR EACH NODE ---
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	Node Canonical(int lv, int idx)
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		Node& x = tree[lv][idx];
ba4dea3538 2012-01-22        kinaba: 		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
ba4dea3538 2012-01-22        kinaba: 		if( !x.switched )
ba4dea3538 2012-01-22        kinaba: 			return x;
ba4dea3538 2012-01-22        kinaba: 		Node n = {-x.sum, -x.minLeft, -x.maxLeft, x.n7, x.n4, false};
ba4dea3538 2012-01-22        kinaba: 		return n;
ba4dea3538 2012-01-22        kinaba: 		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	void UpdateMidNode(int lv, int idx)
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		Node l = Canonical(lv-1, idx*2);
ba4dea3538 2012-01-22        kinaba: 		Node r = Canonical(lv-1, idx*2+1);
ba4dea3538 2012-01-22        kinaba: 		// --- BOTTOM UP COMPUTATION ---
ba4dea3538 2012-01-22        kinaba: 		Node me = {
ba4dea3538 2012-01-22        kinaba: 			l.sum + r.sum,
ba4dea3538 2012-01-22        kinaba: 			max(l.maxLeft, l.sum+r.maxLeft),
ba4dea3538 2012-01-22        kinaba: 			min(l.minLeft, l.sum+r.minLeft),
ba4dea3538 2012-01-22        kinaba: 			l.n4 + r.n4,
ba4dea3538 2012-01-22        kinaba: 			l.n7 + r.n7,
ba4dea3538 2012-01-22        kinaba: 			false
ba4dea3538 2012-01-22        kinaba: 		};
ba4dea3538 2012-01-22        kinaba: 		// --- BOTTOM UP COMPUTATION ---
ba4dea3538 2012-01-22        kinaba: 		tree[lv][idx] = me;
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	vector< vector<Node> > tree;
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: public:
ba4dea3538 2012-01-22        kinaba: 	SegmentTree(const string& s)
ba4dea3538 2012-01-22        kinaba: 	{
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)
ba4dea3538 2012-01-22        kinaba: 		{
ba4dea3538 2012-01-22        kinaba: 			// --- INITIALIZE BASE 1-ELEMENT NODES ---
ba4dea3538 2012-01-22        kinaba: 			int v = i<s.size() ? (s[i]=='4' ? +1 : -1) : 0;
ba4dea3538 2012-01-22        kinaba: 			Node me = {v, max(0,v), min(0,v), v==+1, v==-1, false};
ba4dea3538 2012-01-22        kinaba: 			// --- INITIALIZE BASE 1-ELEMENT NODES ---
ba4dea3538 2012-01-22        kinaba: 			tree.back()[i] = me;
ba4dea3538 2012-01-22        kinaba: 		}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 		while(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)
ba4dea3538 2012-01-22        kinaba: 				UpdateMidNode(tree.size()-1, i);
ba4dea3538 2012-01-22        kinaba: 		}
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	int Count()
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		Node x = Canonical(tree.size()-1, 0);
ba4dea3538 2012-01-22        kinaba: 		return x.maxLeft + x.n7;
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	void Switch(int L, int R)
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		SwitchRec(tree[0].size(), tree.size()-1, 0, L, R);
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 	void SwitchRec(int Stride, int lv, int idx, int Raw_L, int Raw_R)
ba4dea3538 2012-01-22        kinaba: 	{
ba4dea3538 2012-01-22        kinaba: 		// Outside
ba4dea3538 2012-01-22        kinaba: 		if( Raw_R <= Stride*idx || Stride*(idx+1) <= Raw_L )
ba4dea3538 2012-01-22        kinaba: 			return;
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 		// Inside
ba4dea3538 2012-01-22        kinaba: 		bool& me = tree[lv][idx].switched;
ba4dea3538 2012-01-22        kinaba: 		if( Raw_L <= Stride*idx && Stride*(idx+1) <= Raw_R )
ba4dea3538 2012-01-22        kinaba: 		{
ba4dea3538 2012-01-22        kinaba: 			me ^= 1;
ba4dea3538 2012-01-22        kinaba: 			return;
ba4dea3538 2012-01-22        kinaba: 		}
ba4dea3538 2012-01-22        kinaba: 
ba4dea3538 2012-01-22        kinaba: 		// Overlap
ba4dea3538 2012-01-22        kinaba: 		tree[lv-1][idx*2].switched   ^= me;
ba4dea3538 2012-01-22        kinaba: 		tree[lv-1][idx*2+1].switched ^= me;
ba4dea3538 2012-01-22        kinaba: 		SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
ba4dea3538 2012-01-22        kinaba: 		SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
ba4dea3538 2012-01-22        kinaba: 		UpdateMidNode(lv, idx);
ba4dea3538 2012-01-22        kinaba: 	}
ba4dea3538 2012-01-22        kinaba: };
58f56e668e 2012-02-18        kinaba: */