Differences From Artifact [fb4d697dde7b0758]:
- File
lib/dataStructure/segmentTree.cpp
- 2013-12-12 03:04:28 - part of checkin [4db7305442] on branch trunk - Simplify Repeat() example. (user: kinaba) [annotate]
To Artifact [7137a382264b4c89]:
- File
lib/dataStructure/segmentTree.cpp
- 2021-01-28 16:41:41 - part of checkin [f64fed0a88] on branch trunk - segtree fix (user: kinaba) [annotate]
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 698 B (bug fixed)
6 // - Codeforces 200 D 7 // - Codeforces 200 D
7 // - Codeforces 107 C (old version) 8 // - Codeforces 107 C (old version)
8 // - Codeforces 104 E (old version) 9 // - Codeforces 104 E (old version)
9 //------------------------------------------------------------- 10 //-------------------------------------------------------------
10 11
11 class SegmentTree 12 class SegmentTree
12 { 13 {
................................................................................................................................................................................
101 SetRec(s,e,n,lv-1,idx*2+1,stride/2); 102 SetRec(s,e,n,lv-1,idx*2+1,stride/2);
102 CalcMidNode(lv, idx); 103 CalcMidNode(lv, idx);
103 } 104 }
104 } 105 }
105 106
106 void CalcMidNode(int lv, int idx) 107 void CalcMidNode(int lv, int idx)
107 { 108 {
> 109 ResolveLazy(lv-1, idx*2);
> 110 ResolveLazy(lv-1, idx*2+1);
108 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2 111 tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2
109 } 112 }
110 113
111 void ResolveLazy(int lv, int idx) 114 void ResolveLazy(int lv, int idx)
112 { 115 {
113 if(tree[lv][idx].lazy) { 116 if(tree[lv][idx].lazy) {
114 if(lv > 0) { 117 if(lv > 0) {