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: 58f56e668e 2012-02-18 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> 58f56e668e 2012-02-18 kinaba: void Set(int s, int e, Value v) { // seq[s,e):=v : O(log nE|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: */