| 72 | for (int i = 2; i < n; i++) lg[i] = lg[i / 2] + 1; |
| 73 | } |
| 74 | void build() { |
| 75 | int sz = n - 1; |
| 76 | t.resize(sz); |
| 77 | for (int i = 0; i < sz; i++) { |
| 78 | t[i].resize(LG); |
| 79 | t[i][0] = lcp[i]; |
| 80 | } |
| 81 | for (int k = 1; k < LG; ++k) { |
| 82 | for (int i = 0; i + (1 << k) - 1 < sz; ++i) { |
| 83 | t[i][k] = min(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]); |
| 84 | } |
| 85 | } |
| 86 | } |
| 87 | int query(int l, int r) { // minimum of lcp[l], ..., lcp[r] |
| 88 | int k = lg[r - l + 1]; |
| 89 | return min(t[l][k], t[r - (1 << k) + 1][k]); |