ADDED   lib/dataStructure/segmentTree.cpp
Index: lib/dataStructure/segmentTree.cpp
==================================================================
--- lib/dataStructure/segmentTree.cpp
+++ lib/dataStructure/segmentTree.cpp
@@ -0,0 +1,110 @@
+//-------------------------------------------------------------
+// Segment tree
+//   in some general form
+//
+// Verified by
+//   - Codeforces 104 E
+//-------------------------------------------------------------
+
+class SegmentTree
+{
+	// --- DATA FOR EACH NODE ---
+	struct Node
+	{
+		int sum;
+		int maxLeft;
+		int minLeft;
+		int n4;
+		int n7;
+		bool switched;
+	};
+	// --- DATA FOR EACH NODE ---
+
+	Node Canonical(int lv, int idx)
+	{
+		Node& x = tree[lv][idx];
+		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
+		if( !x.switched )
+			return x;
+		Node n = {-x.sum, -x.minLeft, -x.maxLeft, x.n7, x.n4, false};
+		return n;
+		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
+	}
+
+	void UpdateMidNode(int lv, int idx)
+	{
+		Node l = Canonical(lv-1, idx*2);
+		Node r = Canonical(lv-1, idx*2+1);
+		// --- BOTTOM UP COMPUTATION ---
+		Node me = {
+			l.sum + r.sum,
+			max(l.maxLeft, l.sum+r.maxLeft),
+			min(l.minLeft, l.sum+r.minLeft),
+			l.n4 + r.n4,
+			l.n7 + r.n7,
+			false
+		};
+		// --- BOTTOM UP COMPUTATION ---
+		tree[lv][idx] = me;
+	}
+
+	vector< vector<Node> > tree;
+
+public:
+	SegmentTree(const string& s)
+	{
+		int N = 1;
+		while( N < s.size() )
+			N <<= 1;
+
+		tree.resize(tree.size()+1); tree.back().resize(N);
+		for(int i=0; i<N; ++i)
+		{
+			// --- INITIALIZE BASE 1-ELEMENT NODES ---
+			int v = i<s.size() ? (s[i]=='4' ? +1 : -1) : 0;
+			Node me = {v, max(0,v), min(0,v), v==+1, v==-1, false};
+			// --- INITIALIZE BASE 1-ELEMENT NODES ---
+			tree.back()[i] = me;
+		}
+
+		while(N>>=1)
+		{
+			tree.resize(tree.size()+1); tree.back().resize(N);
+			for(int i=0; i<N; ++i)
+				UpdateMidNode(tree.size()-1, i);
+		}
+	}
+
+	int Count()
+	{
+		Node x = Canonical(tree.size()-1, 0);
+		return x.maxLeft + x.n7;
+	}
+
+	void Switch(int L, int R)
+	{
+		SwitchRec(tree[0].size(), tree.size()-1, 0, L, R);
+	}
+
+	void SwitchRec(int Stride, int lv, int idx, int Raw_L, int Raw_R)
+	{
+		// Outside
+		if( Raw_R <= Stride*idx || Stride*(idx+1) <= Raw_L )
+			return;
+
+		// Inside
+		bool& me = tree[lv][idx].switched;
+		if( Raw_L <= Stride*idx && Stride*(idx+1) <= Raw_R )
+		{
+			me ^= 1;
+			return;
+		}
+
+		// Overlap
+		tree[lv-1][idx*2].switched   ^= me;
+		tree[lv-1][idx*2+1].switched ^= me;
+		SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
+		SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
+		UpdateMidNode(lv, idx);
+	}
+};