struct SparseTable { vector> st; ll *a; int better(int lidx, int ridx) { return a[lidx] <= a[ridx] ? lidx : ridx; } void init(vector* vec) { int n = sz(*vec); a = vec->data(); st.assign(__lg(n) + 1, vector(n)); iota(all(st[0]), 0); for (int j = 0; (2 << j) <= n; j++) { for (int i = 0; i + (2 << j) <= n; i++) { st[j + 1][i] = better(st[j][i] , st[j][i + (1 << j)]); }}} int queryIdempotent(int l, int r) { if (r <= l) return -1; int j = __lg(r - l); //31 - builtin_clz(r - l); return better(st[j][l] , st[j][r - (1 << j)]); } }; > cgit logo index : tcr
Team Contest Reference
summaryrefslogtreecommitdiff
path: root/content/datastructures/dynamicConvexHull.cpp
blob: 63e0e13aa0d003b4a684bb2c036e42bd6bbe86af (plain) 
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