1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include "../utility.h"
#include <algorithm>
namespace meow{
template<class Value>
inline void
SegmentTree<Value>::update(size_t __i, size_t __size, Value const& __value,
bool __over){
if(__over){
_nodes[__i]._value = __value * __size;
_nodes[__i]._offset = __value;
_nodes[__i]._sameFlag = true;
}else{
_nodes[__i]._value = _nodes[__i]._value + __value * __size;
_nodes[__i]._offset = _nodes[__i]._offset + __value;
}
}
template<class Value>
inline void
SegmentTree<Value>::update(size_t __l, size_t __r, size_t __L, size_t __R,
size_t __i, Value const& __value,
bool __over){
if(__l == __L && __r == __R){
update(__i, __R - __L + 1, __value, __over);
return ;
}
size_t mid = (__L + __R) / 2;
if(__L < __R){
update(__i*2+1, mid-__L+1, _nodes[__i]._offset, _nodes[__i]._sameFlag);
update(__i*2+2, __R - mid, _nodes[__i]._offset, _nodes[__i]._sameFlag);
_nodes[__i]._offset = Value(0);
_nodes[__i]._sameFlag = false;
}
if (__r <= mid) update(__l,__r, __L ,mid, __i*2+1, __value, __over);
else if(mid+1 <= __l) update(__l,__r, mid+1,__R, __i*2+2, __value, __over);
else{
update(__l,mid , __L,mid , __i*2+1, __value, __over);
update( mid+1, __r, mid+1, __R, __i*2+2, __value, __over);
}
_nodes[__i]._value = (
(_nodes[__i * 2 + 1]._value | _nodes[__i * 2 + 2]._value)
+ _nodes[__i]._offset
);
}
template<class Value>
inline Value
SegmentTree<Value>::query(size_t __l, size_t __r, size_t __L, size_t __R,
size_t __i){
if(__l == __L && __r == __R) return _nodes[__i]._value;
Value off = _nodes[__i]._offset * (__r - __l + 1);
if(_nodes[__i]._sameFlag) return off;
size_t mid = (__L + __R) / 2;
if (__r <= mid) return query(__l,__r, __L , mid, __i*2+1) + off;
else if(mid+1 <= __l) return query(__l,__r, mid+1, __R, __i*2+2) + off;
else{
return ( query(__l, mid , __L, mid, __i*2+1)
| query( mid+1, __r, mid+1, __R, __i*2+2)
) + off;
}
}
//
template<class Value>
inline bool
SegmentTree<Value>::rangeCorrect(ssize_t* __first, ssize_t* __last) const{
if(*__last<*__first || *__last<0 || _size-1<*__first) return false;
*__first = inRange((ssize_t)0, (ssize_t)_size - 1, *__first);
*__last = inRange((ssize_t)0, (ssize_t)_size - 1, *__last );
return true;
}
//
template<class Value>
inline SegmentTree<Value>::SegmentTree(){ reset(1); }
template<class Value>
inline SegmentTree<Value>::SegmentTree(size_t __size){ reset(__size); }
template<class Value>
inline SegmentTree<Value>::SegmentTree(SegmentTree const& __tree2):
_size(__tree2._size), _nodes(__tree2._nodes){ }
//
template<class Value>
inline void
SegmentTree<Value>::reset(size_t __size){
_size = std::max(__size, (size_t)1);
_nodes.resize(__size * 4);
_nodes[0]._sameFlag = true;
_nodes[0]._value = Value(0);
_nodes[0]._offset = Value(0);
}
template<class Value>
inline Value
SegmentTree<Value>::query(ssize_t __first, ssize_t __last) const{
if(rangeCorrect(&__first, &__last) == false) return Value();
return ((SegmentTree*)this)->query(__first, __last, 0, _size - 1, 0);
}
template<class Value>
inline void
SegmentTree<Value>::override(ssize_t __first, ssize_t __last,
Value const& __value){
if(rangeCorrect(&__first, &__last) == false) return ;
update(__first, __last, 0, _size - 1, 0, __value, true);
}
template<class Value>
inline void
SegmentTree<Value>::offset(ssize_t __first, ssize_t __last,
Value const& __delta){
if(rangeCorrect(&__first, &__last) == false) return ;
update(__first, __last, 0, _size - 1, 0, __delta, false);
}
}
|
