Overview
| SHA1 Hash: | f64fed0a888e20b12b79a83fd51d6483b4a0e8e3 |
|---|---|
| Date: | 2021-01-28 16:41:41 |
| User: | kinaba |
| Comment: | segtree fix |
| 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 [fb4d697dde7b0758] to [7137a382264b4c89].
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) {