/
dual.cpp
59 lines (52 loc) · 1.01 KB
/
dual.cpp
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
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template <typename E>
struct SegmentTree{
using H = function<E(E,E)>;
int n,height;
H h;
E ei;
vector<E> laz;
SegmentTree(H h,E ei):h(h),ei(ei){}
void init(int n_){
n=1;height=0;
while(n<n_) n<<=1,height++;
laz.assign(2*n,ei);
}
inline void propagate(int k){
if(laz[k]==ei) return;
laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
laz[k]=ei;
}
inline void thrust(int k){
for(int i=height;i;i--) propagate(k>>i);
}
void update(int a,int b,E x){
if(a>=b) return;
thrust(a+=n);
thrust(b+=n-1);
for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
if(l&1) laz[l]=h(laz[l],x),l++;
if(r&1) --r,laz[r]=h(laz[r],x);
}
}
E get_val(int a){
thrust(a+=n);
return laz[a];
}
void set_val(int a,E x){
thrust(a+=n);
laz[a]=x;
}
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
return 0;
}
#endif