/
xor_segtree.hpp
90 lines (83 loc) · 2.05 KB
/
xor_segtree.hpp
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
// set,prod どちらも O(sqrt(N)) 時間。
// モノイドが可換なら普通のセグ木を使うこと。
template <class Monoid>
struct Xor_SegTree {
static_assert(!Monoid::commute);
using MX = Monoid;
using X = typename MX::value_type;
using value_type = X;
vvc<X> dat;
int n, log, size;
int H; // 幅 2^H のところまで作る
Xor_SegTree() {}
Xor_SegTree(int n) { build(n); }
template <typename F>
Xor_SegTree(int n, F f) {
build(n, f);
}
Xor_SegTree(const vc<X>& v) { build(v); }
void build(int m) {
build(m, [](int i) -> X { return MX::unit(); });
}
void build(const vc<X>& v) {
build(len(v), [&](int i) -> X { return v[i]; });
}
template <typename F>
void build(int m, F f) {
n = m, log = 1;
while ((1 << log) < n) ++log;
size = 1 << log;
assert(n == size);
H = log / 2;
dat.assign(H + 1, vc<X>(size));
FOR(i, n) dat[0][i] = f(i);
FOR(h, 1, H + 1) FOR(i, n >> h) { update(h, i); }
}
X get(int i) { return dat[0][i]; }
vc<X> get_all() { return dat[0]; }
void update(int h, int i) {
assert(0 < h && h <= H);
int cnt = 1 << (h - 1);
int a = i << h;
int b = a + cnt;
FOR(k, cnt) {
dat[h][a + k] = MX::op(dat[h - 1][a + k], dat[h - 1][b + k]);
dat[h][b + k] = MX::op(dat[h - 1][b + k], dat[h - 1][a + k]);
}
}
void set(int i, const X& x) {
assert(i < n);
dat[0][i] = x;
FOR(h, 1, H + 1) {
i /= 2;
update(h, i);
}
}
void multiply(int i, const X& x) {
assert(i < n);
dat[0][i] = MX::op(dat[0][i], x);
FOR(h, 1, H + 1) {
i /= 2;
update(h, i);
}
}
X prod(int L, int R, int xor_val) {
X x1 = MX::unit(), x2 = MX::unit();
FOR(h, H) {
if (L >= R) break;
if (L & (1 << h)) {
x1 = MX::op(x1, dat[h][L ^ xor_val]);
L += 1 << h;
}
if (R & (1 << h)) {
R -= 1 << h;
x2 = MX::op(dat[h][R ^ xor_val], x2);
}
}
while (L < R) {
x1 = MX::op(x1, dat[H][L ^ xor_val]);
L += 1 << H;
}
return MX::op(x1, x2);
}
};