基于压位与猫树分治的 O(n)-O(1) 的 RMQ
老实倍增,很枯燥吧。下文以
简介
这是一种在 Word-RAM Model 下被认为是时间复杂度
做法
下文默认假装将
考虑猫树分治解决 RMQ 问题的过程。我们建立一颗类似线段树的树,并在每个节点维护所有左半区间的后缀与右半区间的前缀的
现在考虑我们不记录具体的
尝试将时间复杂度也压到这个部分。由于我们查询的时候需要查询前缀/后缀的
于是分为得到这些位向量和预处理支持
现在考虑所有右半的前缀,左半的后缀同理。考察一个向上合并两个儿子区间的过程。一开始,所有节点内部区间就是这个位置,因此所有位置都是前缀
因此,某个位置在猫树上作为前缀
现在考虑快速得到这个位置
现在得到位向量以后,考虑预处理以支持
于是我们得到了一个
实现
这是一份能通过 P3865 【模板】ST 表 & RMQ 问题 的代码。
#include <bits/stdc++.h>
#define N 100010
#define ull unsigned long long
#define clz __builtin_clzll
#define ctz __builtin_ctzll
using namespace std;
int n, m;
int a[N];
int stk[N], tp;
int l[N], r[N];
struct info { ull pv, sv; int pre, suf; }T[18][(N >> 6) + 1];
inline int hb(unsigned x) { return 31 - __builtin_clz(x); }
inline int qry(int l, int r)
{
if (l == r) return l;
static ull s, p;
static int h, u, v;
h = hb(l ^ r);
const info& x = T[h][l >> 6], & y = T[h][r >> 6];
s = x.sv & (~0ull << (l & 63)), p = y.pv & (~0ull >> (~r & 63));
u = s ? (l & ~63) + ctz(s) : x.suf, v = p ? (r & ~63) + 63 - clz(p) : y.pre;
return a[u] > a[v] ? u : v;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
while (tp && a[stk[tp]] < a[i]) r[stk[tp--]] = i;
l[i] = stk[tp], stk[++tp] = i;
}
while (tp) r[stk[tp--]] = n + 1;
for (int i = 1; i <= n; i++) T[l[i] ? hb(l[i] ^ i) : 17][i >> 6].pv |= 1ull << (i & 63), T[r[i] != n + 1 ? hb(r[i] ^ i) : 17][i >> 6].sv |= 1ull << (i & 63);
for (int p = 17; ~p; p--)
{
if (p != 17) for (int i = 0; i <= n >> 6; i++) T[p][i].pv |= T[p + 1][i].pv, T[p][i].sv |= T[p + 1][i].sv;
int pos = 0;
for (int i = 0; i <= n >> 6; i++) T[p][i].pre = pos, pos = T[p][i].pv ? (i << 6) + 63 - clz(T[p][i].pv) : pos;
pos = 0;
for (int i = n >> 6; ~i; i--) T[p][i].suf = pos, pos = T[p][i].sv ? (i << 6) + ctz(T[p][i].sv) : pos;
}
static int l, r;
while (m--) cin >> l >> r, cout << a[qry(l, r)] << '\n';
return 0;
}
可以看到实现难度跟基于压位的倍增表大差不差。
后记
本做法由我在学习小波树的时候,神游之时思考到的一种做法。也是在退役之前希望给 OI 做出点贡献吧。