Index: lib/dataStructure/segmentTree.cpp
==================================================================
--- lib/dataStructure/segmentTree.cpp
+++ lib/dataStructure/segmentTree.cpp
@@ -1,17 +1,46 @@
//-------------------------------------------------------------
// Segment tree
// in some general form
//
// Verified by
-// - Codeforces 107 C
-// - Codeforces 104 E
+// - Codeforces 200 D
+// - Codeforces 107 C (old version)
+// - Codeforces 104 E (old version)
//-------------------------------------------------------------
-template<typename Node>
class SegmentTree
{
+ struct Node
+ {
+ int sum;
+
+ static Node Zero()
+ {
+ Node c = {0};
+ return c;
+ }
+ static Node One(int v)
+ {
+ Node c = {v};
+ return c;
+ }
+ static Node Concat(const Node& l, const Node& r)
+ {
+ Node c = {l.sum + r.sum};
+ return c;
+ }
+ static Node Repeat(const Node& n, int k)
+ {
+ if(k==0) return Zero();
+ Node c = {n.sum * k};
+ return c;
+ }
+
+ bool lazy;
+ };
+
public:
template<typename Seq>
SegmentTree(const Seq& s) {
int N = 1;
while( N < s.size() )
@@ -31,26 +60,23 @@
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 n |e-s|)
+ void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n)
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();
+ ResolveLazy(lv, idx);
+
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));
}
@@ -59,149 +85,40 @@
{
const int myL = stride*idx;
const int myR = stride*(idx+1);
if( e<=myL || myR<=s )
return;
+ ResolveLazy(lv, idx);
+
if( stride == 1 ) {
tree[lv][idx] = n;
} else {
+ if( s<=myL && myR<=e ) {
+ tree[lv][idx] = n;
+ tree[lv][idx].lazy = true;
+ ResolveLazy(lv, idx);
+ return;
+ }
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;
-};
+ void CalcMidNode(int lv, int idx)
+ {
+ tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
+ }
-struct Node
-{
- double sum;
- double maxLeft;
- double maxRight;
- double maxSum;
- static Node Zero()
+ void ResolveLazy(int lv, int idx)
{
- 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;
+ if(tree[lv][idx].lazy) {
+ if(lv > 0) {
+ tree[lv-1][idx*2] = tree[lv][idx];
+ tree[lv-1][idx*2+1] = tree[lv][idx];
+ }
+ tree[lv][idx] = Node::Repeat(tree[lv][idx], 1<<lv);
+ }
}
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);
- }
};
-*/
ADDED lib/graph/treeDfsNumbering.cpp
Index: lib/graph/treeDfsNumbering.cpp
==================================================================
--- lib/graph/treeDfsNumbering.cpp
+++ lib/graph/treeDfsNumbering.cpp
@@ -0,0 +1,42 @@
+//-------------------------------------------------------------
+// Tree DFS numbering
+// O(N)
+//
+// G : adjacent list of a graph (forming a tree)
+// Labels each node v as dfs[v].
+// Inclusive [dfs[v], dfs_end[v]] denotes the descendant range.
+//
+// Verified by
+// - Codeforces 200 Div1 D
+//-------------------------------------------------------------
+
+void dfs_numbering(
+ int root,
+ const vector<vector<int>>& G, vector<int>& dfs, vector<int>& dfs_end,
+ vector<int>& parent_of)
+{
+ int dfs_number = root;
+ dfs[root] = dfs_number++;
+ parent_of[root] = -1;
+
+ stack<tuple<int,int,int>> stk;
+ stk.push(make_tuple(-1, root, 0));
+ while(!stk.empty()) {
+ int grandparent = get<0>(stk.top());
+ int parent = get<1>(stk.top());
+ int child_id = get<2>(stk.top());
+ stk.pop();
+ if(G[parent].size() <= child_id) {
+ dfs_end[parent] = dfs_number - 1;
+ continue;
+ }
+ stk.push(make_tuple(grandparent, parent, child_id+1));
+
+ int me = G[parent][child_id];
+ if(me != grandparent) {
+ dfs[me] = dfs_number++;
+ parent_of[me] = parent;
+ stk.push(make_tuple(parent, me, 0));
+ }
+ }
+}