Overview
| SHA1 Hash: | 94afd8e13cf86e83db67616d1462550ad8a93f72 |
|---|---|
| Date: | 2013-09-14 20:29:31 |
| User: | kinaba |
| Comment: | Segment tree with range update. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/dataStructure/segmentTree.cpp from [f9b609a5f0b95ebf] to [b7ca5af5f1eab32a].
1 1 //------------------------------------------------------------- 2 2 // Segment tree 3 3 // in some general form 4 4 // 5 5 // Verified by 6 -// - Codeforces 107 C 7 -// - Codeforces 104 E 6 +// - Codeforces 200 D 7 +// - Codeforces 107 C (old version) 8 +// - Codeforces 104 E (old version) 8 9 //------------------------------------------------------------- 9 10 10 -template<typename Node> 11 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 42 public: 14 43 template<typename Seq> 15 44 SegmentTree(const Seq& s) { 16 45 int N = 1; 17 46 while( N < s.size() ) 18 47 N <<= 1; 19 48 ................................................................................ 29 58 } 30 59 31 60 Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n) 32 61 return QueryRec(s, e, tree.size()-1, 0, tree[0].size()); 33 62 } 34 63 35 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 66 SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size()); 38 67 } 39 68 40 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+1]); 44 - } 45 - 46 70 Node QueryRec(int s, int e, int lv, int idx, int stride) 47 71 { 48 72 const int myL = stride*idx; 49 73 const int myR = stride*(idx+1); 50 74 if( e<=myL || myR<=s ) 51 75 return Node::Zero(); 76 + ResolveLazy(lv, idx); 77 + 52 78 if( s<=myL && myR<=e ) 53 79 return tree[lv][idx]; 54 80 return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2), 55 81 QueryRec(s,e,lv-1,idx*2+1,stride/2)); 56 82 } 57 83 58 84 void SetRec(int s, int e, const Node& n, int lv, int idx, int stride) 59 85 { 60 86 const int myL = stride*idx; 61 87 const int myR = stride*(idx+1); 62 88 if( e<=myL || myR<=s ) 63 89 return; 90 + ResolveLazy(lv, idx); 91 + 64 92 if( stride == 1 ) { 65 93 tree[lv][idx] = n; 66 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 101 SetRec(s,e,n,lv-1,idx*2,stride/2); 68 102 SetRec(s,e,n,lv-1,idx*2+1,stride/2); 69 103 CalcMidNode(lv, idx); 70 104 } 71 105 } 72 106 73 - vector< vector<Node> > tree; 74 -}; 107 + void CalcMidNode(int lv, int idx) 108 + { 109 + tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]); 110 + } 75 111 76 -struct Node 77 -{ 78 - double sum; 79 - double maxLeft; 80 - double maxRight; 81 - double maxSum; 82 - static Node Zero() 112 + void ResolveLazy(int lv, int idx) 83 113 { 84 - Node c = {0, 0, 0, 0}; 85 - return c; 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]; 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 --- 128 - } 129 - 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; 114 + if(tree[lv][idx].lazy) { 115 + if(lv > 0) { 116 + tree[lv-1][idx*2] = tree[lv][idx]; 117 + tree[lv-1][idx*2+1] = tree[lv][idx]; 118 + } 119 + tree[lv][idx] = Node::Repeat(tree[lv][idx], 1<<lv); 120 + } 145 121 } 146 122 147 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 -*/
Added lib/graph/treeDfsNumbering.cpp version [4b76a9848cd0e992]
1 +//------------------------------------------------------------- 2 +// Tree DFS numbering 3 +// O(N) 4 +// 5 +// G : adjacent list of a graph (forming a tree) 6 +// Labels each node v as dfs[v]. 7 +// Inclusive [dfs[v], dfs_end[v]] denotes the descendant range. 8 +// 9 +// Verified by 10 +// - Codeforces 200 Div1 D 11 +//------------------------------------------------------------- 12 + 13 +void dfs_numbering( 14 + int root, 15 + const vector<vector<int>>& G, vector<int>& dfs, vector<int>& dfs_end, 16 + vector<int>& parent_of) 17 +{ 18 + int dfs_number = root; 19 + dfs[root] = dfs_number++; 20 + parent_of[root] = -1; 21 + 22 + stack<tuple<int,int,int>> stk; 23 + stk.push(make_tuple(-1, root, 0)); 24 + while(!stk.empty()) { 25 + int grandparent = get<0>(stk.top()); 26 + int parent = get<1>(stk.top()); 27 + int child_id = get<2>(stk.top()); 28 + stk.pop(); 29 + if(G[parent].size() <= child_id) { 30 + dfs_end[parent] = dfs_number - 1; 31 + continue; 32 + } 33 + stk.push(make_tuple(grandparent, parent, child_id+1)); 34 + 35 + int me = G[parent][child_id]; 36 + if(me != grandparent) { 37 + dfs[me] = dfs_number++; 38 + parent_of[me] = parent; 39 + stk.push(make_tuple(parent, me, 0)); 40 + } 41 + } 42 +}