Differences From Artifact [f9b609a5f0b95ebf]:
- File
lib/dataStructure/segmentTree.cpp
- 2012-06-07 14:24:24 - part of checkin [34dd53bac9] on branch trunk - TCO12-2C (user: kinaba) [annotate]
To Artifact [b7ca5af5f1eab32a]:
- File
lib/dataStructure/segmentTree.cpp
- 2013-09-14 20:29:31 - part of checkin [94afd8e13c] on branch trunk - Segment tree with range update. (user: kinaba) [annotate]
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 -*/