Artifact Content
Not logged in

Artifact 0226be12935bcdf471d13b7a32e02813068ec2b1


//-------------------------------------------------------------
// Segment tree
//   in some general form
//
// Verified by
//   - Codeforces 107 C
//   - Codeforces 104 E
//-------------------------------------------------------------

template<typename Node>
class SegmentTree
{
public:
	template<typename Seq>
	SegmentTree(const Seq& 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)
			tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero();

		while(N>>=1) {
			tree.resize(tree.size()+1); tree.back().resize(N);
			for(int i=0; i<N; ++i)
				CalcMidNode(tree.size()-1, i);
		}
	}

	Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
		return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
	}

	template<typename Value>
	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log nE|e-s|)
		SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
	}

private:
	void CalcMidNode(int lv, int idx)
	{
		tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
	}

	Node QueryRec(int s, int e, int lv, int idx, int stride)
	{
		const int myL = stride*idx;
		const int myR = stride*(idx+1);
		if( e<=myL || myR<=s )
			return Node::Zero();
		if( s<=myL && myR<=e )
			return tree[lv][idx];
		return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
		                    QueryRec(s,e,lv-1,idx*2+1,stride/2));
	}

	void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
	{
		const int myL = stride*idx;
		const int myR = stride*(idx+1);
		if( e<=myL || myR<=s )
			return;
		if( stride == 1 ) {
			tree[lv][idx] = n;
		} else {
			SetRec(s,e,n,lv-1,idx*2,stride/2);
			SetRec(s,e,n,lv-1,idx*2+1,stride/2);
			CalcMidNode(lv, idx);
		}
	}

	vector< vector<Node> > tree;
};

struct Node
{
	double sum;
	double maxLeft;
	double maxRight;
	double maxSum;
	static Node Zero()
	{
		Node c = {0, 0, 0, 0};
		return c;
	}
	static Node One(double v)
	{
		Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
		return c;
	}
	static Node Concat(const Node& l, const Node& r)
	{
		Node c = {
			l.sum + r.sum,
			max(l.maxLeft, l.sum+r.maxLeft),
			max(l.maxRight+r.sum, r.maxRight),
			max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
		};
		return c;
	}
};

/*
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);
	}
};
*/