|
| 1 | +#include <vector> |
| 2 | +#include <cassert> |
| 3 | +#include <functional> |
| 4 | + |
| 5 | +template <class T, class Compare = std::less<T>> |
| 6 | +class SchieberVishkinRMQ { |
| 7 | +public: |
| 8 | + SchieberVishkinRMQ() = default; |
| 9 | + |
| 10 | + void build(const std::vector<T> &a) { |
| 11 | + build(a.data(), a.size()); |
| 12 | + } |
| 13 | + |
| 14 | + void build(const T *a, int n) { |
| 15 | + std::vector<int> left(n, -1), right(n, -1); |
| 16 | + std::vector<int> stk(n); |
| 17 | + // build Cartesian Tree |
| 18 | + for (int i = 0, top = 0; i < n; ++i) { |
| 19 | + int last = -1; |
| 20 | + while (top && compare(a[i], a[stk[top - 1]])) { |
| 21 | + last = stk[--top]; |
| 22 | + } |
| 23 | + if (top) right[stk[top - 1]] = i; |
| 24 | + left[i] = last; |
| 25 | + stk[top++] = i; |
| 26 | + } |
| 27 | + |
| 28 | + // find preorder |
| 29 | + int root = stk[0]; |
| 30 | + std::vector<int> parents(n, -1), order; |
| 31 | + indices.resize(n), inlabel.resize(n); |
| 32 | + for (int top = 1; top; ) { |
| 33 | + int u = stk[--top]; |
| 34 | + order.push_back(u); |
| 35 | + indices[u] = inlabel[u] = order.size(); |
| 36 | + if (left[u] != -1) { |
| 37 | + stk[top++] = left[u]; |
| 38 | + parents[left[u]] = u; |
| 39 | + } |
| 40 | + if (right[u] != -1) { |
| 41 | + stk[top++] = right[u]; |
| 42 | + parents[right[u]] = u; |
| 43 | + } |
| 44 | + } |
| 45 | + |
| 46 | + // calc helper structures for Schieber-Vishkin LCA |
| 47 | + ascendant.resize(n), head.resize(n); |
| 48 | + for (int i = n - 1; i > 0; --i) { |
| 49 | + int v = order[i], p = parents[v]; |
| 50 | + if (lowbit(inlabel[p]) < lowbit(inlabel[v])) { |
| 51 | + inlabel[p] = inlabel[v]; |
| 52 | + } |
| 53 | + } |
| 54 | + ascendant[root] = 0; |
| 55 | + for (int i = 1; i < n; ++i) { |
| 56 | + int v = order[i], p = parents[v]; |
| 57 | + ascendant[v] = ascendant[p] | lowbit(inlabel[v]); |
| 58 | + } |
| 59 | + head[0] = root; |
| 60 | + for (int i = 1; i < n; ++i) { |
| 61 | + int v = order[i], p = parents[v]; |
| 62 | + if (inlabel[v] != inlabel[p]) head[indices[v] - 1] = p; |
| 63 | + else head[indices[v] - 1] = head[indices[p] - 1]; |
| 64 | + } |
| 65 | + } |
| 66 | + |
| 67 | + // return the index of the minimum value in [u, v] in O(1) |
| 68 | + int query(int u, int v) const { |
| 69 | + uint Iv = inlabel[v], Iu = inlabel[u]; |
| 70 | + uint hIv = lowbit(Iv), hIu = lowbit(Iu); |
| 71 | + uint mask = highbit((Iv ^ Iu) | hIv | hIu) - 1; |
| 72 | + uint j = lowbit(ascendant[v] & ascendant[u] & ~mask); |
| 73 | + int x, y; |
| 74 | + if (j == hIv) x = v; |
| 75 | + else { |
| 76 | + mask = highbit(ascendant[v] & (j - 1)) - 1; |
| 77 | + x = head[(indices[v] & ~mask | (mask + 1)) - 1]; |
| 78 | + } |
| 79 | + if (j == hIu) y = u; |
| 80 | + else { |
| 81 | + mask = highbit(ascendant[u] & (j - 1)) - 1; |
| 82 | + y = head[(indices[u] & ~mask | (mask + 1)) - 1]; |
| 83 | + } |
| 84 | + return indices[x] < indices[y] ? x : y; |
| 85 | + } |
| 86 | + |
| 87 | +private: |
| 88 | + using uint = unsigned int; |
| 89 | + static uint lowbit(uint x) { |
| 90 | + return x & ~x + 1; // x & (-x) or x & (x ^ (x - 1)) |
| 91 | + } |
| 92 | + static uint highbit(uint x) { |
| 93 | + return 1u << (31 - __builtin_clz(x)); |
| 94 | + } |
| 95 | + |
| 96 | + Compare compare; |
| 97 | + std::vector<uint> indices; |
| 98 | + std::vector<uint> inlabel; |
| 99 | + std::vector<uint> ascendant; |
| 100 | + std::vector<int> head; |
| 101 | +}; |
0 commit comments