1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // Segment tree 2 // Segment tree 3 // in some general form 3 // in some general form 4 // 4 // 5 // Verified by 5 // Verified by 6 // - Codeforces 107 C | 6 // - Codeforces 200 D > 7 // - Codeforces 107 C (old version) 7 // - Codeforces 104 E | 8 // - Codeforces 104 E (old version) 8 //------------------------------------------------------------- 9 //------------------------------------------------------------- 9 10 10 template<typename Node> < 11 class SegmentTree 11 class SegmentTree 12 { 12 { > 13 struct Node > 14 { > 15 int sum; > 16 > 17 static Node Zero() > 18 { > 19 Node c = {0}; > 20 return c; > 21 } > 22 static Node One(int v) > 23 { > 24 Node c = {v}; > 25 return c; > 26 } > 27 static Node Concat(const Node& l, const Node& r) > 28 { > 29 Node c = {l.sum + r.sum}; > 30 return c; > 31 } > 32 static Node Repeat(const Node& n, int k) > 33 { > 34 if(k==0) return Zero(); > 35 Node c = {n.sum * k}; > 36 return c; > 37 } > 38 > 39 bool lazy; > 40 }; > 41 13 public: 42 public: 14 template<typename Seq> 43 template<typename Seq> 15 SegmentTree(const Seq& s) { 44 SegmentTree(const Seq& s) { 16 int N = 1; 45 int N = 1; 17 while( N < s.size() ) 46 while( N < s.size() ) 18 N <<= 1; 47 N <<= 1; 19 48 ................................................................................................................................................................................ 29 } 58 } 30 59 31 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) 60 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) 32 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 61 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 33 } 62 } 34 63 35 template<typename Value> 64 template<typename Value> 36 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|) | 65 void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n) 37 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 66 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 38 } 67 } 39 68 40 private: 69 private: 41 void CalcMidNode(int lv, int idx) < 42 { < 43 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2 < 44 } < 45 < 46 Node QueryRec(int s, int e, int lv, int idx, int stride) 70 Node QueryRec(int s, int e, int lv, int idx, int stride) 47 { 71 { 48 const int myL = stride*idx; 72 const int myL = stride*idx; 49 const int myR = stride*(idx+1); 73 const int myR = stride*(idx+1); 50 if( e<=myL || myR<=s ) 74 if( e<=myL || myR<=s ) 51 return Node::Zero(); 75 return Node::Zero(); > 76 ResolveLazy(lv, idx); > 77 52 if( s<=myL && myR<=e ) 78 if( s<=myL && myR<=e ) 53 return tree[lv][idx]; 79 return tree[lv][idx]; 54 return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2), 80 return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2), 55 QueryRec(s,e,lv-1,idx*2+1,stride/2)); 81 QueryRec(s,e,lv-1,idx*2+1,stride/2)); 56 } 82 } 57 83 58 void SetRec(int s, int e, const Node& n, int lv, int idx, int stride) 84 void SetRec(int s, int e, const Node& n, int lv, int idx, int stride) 59 { 85 { 60 const int myL = stride*idx; 86 const int myL = stride*idx; 61 const int myR = stride*(idx+1); 87 const int myR = stride*(idx+1); 62 if( e<=myL || myR<=s ) 88 if( e<=myL || myR<=s ) 63 return; 89 return; > 90 ResolveLazy(lv, idx); > 91 64 if( stride == 1 ) { 92 if( stride == 1 ) { 65 tree[lv][idx] = n; 93 tree[lv][idx] = n; 66 } else { 94 } else { > 95 if( s<=myL && myR<=e ) { > 96 tree[lv][idx] = n; > 97 tree[lv][idx].lazy = true; > 98 ResolveLazy(lv, idx); > 99 return; > 100 } 67 SetRec(s,e,n,lv-1,idx*2,stride/2); 101 SetRec(s,e,n,lv-1,idx*2,stride/2); 68 SetRec(s,e,n,lv-1,idx*2+1,stride/2); 102 SetRec(s,e,n,lv-1,idx*2+1,stride/2); 69 CalcMidNode(lv, idx); 103 CalcMidNode(lv, idx); 70 } 104 } 71 } 105 } 72 106 73 vector< vector<Node> > tree; | 107 void CalcMidNode(int lv, int idx) 74 }; < > 108 { > 109 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2 > 110 } 75 111 76 struct Node | 112 void ResolveLazy(int lv, int idx) 77 { < 78 double sum; < 79 double maxLeft; < 80 double maxRight; < 81 double maxSum; < 82 static Node Zero() < 83 { 113 { 84 Node c = {0, 0, 0, 0}; | 114 if(tree[lv][idx].lazy) { 85 return c; | 115 if(lv > 0) { 86 } < 87 static Node One(double v) < 88 { < 89 Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)}; < 90 return c; < 91 } < 92 static Node Concat(const Node& l, const Node& r) < 93 { < 94 Node c = { < 95 l.sum + r.sum, < 96 max(l.maxLeft, l.sum+r.maxLeft), < 97 max(l.maxRight+r.sum, r.maxRight), < 98 max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft), < 99 }; < 100 return c; < 101 } < 102 }; < 103 < 104 /* < 105 class SegmentTree < 106 { < 107 // --- DATA FOR EACH NODE --- < 108 struct Node < 109 { < 110 int sum; < 111 int maxLeft; < 112 int minLeft; < 113 int n4; < 114 int n7; < 115 bool switched; < 116 }; < 117 // --- DATA FOR EACH NODE --- < 118 < 119 Node Canonical(int lv, int idx) < 120 { < 121 Node& x = tree[lv][idx]; | 116 tree[lv-1][idx*2] = tree[lv][idx]; 122 // --- DO SOMETHING IF YOU NEED CANONICALIZATION --- < 123 if( !x.switched ) < 124 return x; < 125 Node n = {-x.sum, -x.minLeft, -x.maxLeft, x.n7, x.n4, false}; < 126 return n; < 127 // --- DO SOMETHING IF YOU NEED CANONICALIZATION --- < > 117 tree[lv-1][idx*2+1] = tree[lv][idx]; 128 } | 118 } > 119 tree[lv][idx] = Node::Repeat(tree[lv][idx], 1<<lv); 129 | 120 } 130 void UpdateMidNode(int lv, int idx) < 131 { < 132 Node l = Canonical(lv-1, idx*2); < 133 Node r = Canonical(lv-1, idx*2+1); < 134 // --- BOTTOM UP COMPUTATION --- < 135 Node me = { < 136 l.sum + r.sum, < 137 max(l.maxLeft, l.sum+r.maxLeft), < 138 min(l.minLeft, l.sum+r.minLeft), < 139 l.n4 + r.n4, < 140 l.n7 + r.n7, < 141 false < 142 }; < 143 // --- BOTTOM UP COMPUTATION --- < 144 tree[lv][idx] = me; < 145 } 121 } 146 122 147 vector< vector<Node> > tree; 123 vector< vector<Node> > tree; 148 < 149 public: < 150 SegmentTree(const string& s) < 151 { < 152 int N = 1; < 153 while( N < s.size() ) < 154 N <<= 1; < 155 < 156 tree.resize(tree.size()+1); tree.back().resize(N); < 157 for(int i=0; i<N; ++i) < 158 { < 159 // --- INITIALIZE BASE 1-ELEMENT NODES --- < 160 int v = i<s.size() ? (s[i]=='4' ? +1 : -1) : 0; < 161 Node me = {v, max(0,v), min(0,v), v==+1, v==-1, false}; < 162 // --- INITIALIZE BASE 1-ELEMENT NODES --- < 163 tree.back()[i] = me; < 164 } < 165 < 166 while(N>>=1) < 167 { < 168 tree.resize(tree.size()+1); tree.back().resize(N); < 169 for(int i=0; i<N; ++i) < 170 UpdateMidNode(tree.size()-1, i); < 171 } < 172 } < 173 < 174 int Count() < 175 { < 176 Node x = Canonical(tree.size()-1, 0); < 177 return x.maxLeft + x.n7; < 178 } < 179 < 180 void Switch(int L, int R) < 181 { < 182 SwitchRec(tree[0].size(), tree.size()-1, 0, L, R); < 183 } < 184 < 185 void SwitchRec(int Stride, int lv, int idx, int Raw_L, int Raw_R) < 186 { < 187 // Outside < 188 if( Raw_R <= Stride*idx || Stride*(idx+1) <= Raw_L ) < 189 return; < 190 < 191 // Inside < 192 bool& me = tree[lv][idx].switched; < 193 if( Raw_L <= Stride*idx && Stride*(idx+1) <= Raw_R ) < 194 { < 195 me ^= 1; < 196 return; < 197 } < 198 < 199 // Overlap < 200 tree[lv-1][idx*2].switched ^= me; < 201 tree[lv-1][idx*2+1].switched ^= me; < 202 SwitchRec(Stride/2, lv-1, idx*2, Raw_L, Raw_R); < 203 SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R); < 204 UpdateMidNode(lv, idx); < 205 } < 206 }; 124 }; 207 */ <