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