猫(娘)树
猫树是一种不支持修改、只支持快速查询的数据结构,常用于处理询问复杂度较大的静态问题。
猫树
猫树和线段树的结构相同,因此可以直接借用线段树的结构图。
假设要查询区间
例如查询
找到 LCA 之后该做什么?可以在每个节点维护一个
因为需要求后缀和与前缀和,设一次合并的复杂度为
但问题在于还需要求 LCA。真的要使用 Tarjan 或 ST 表吗?那样空间可能会比较吃紧。
因此可以把原序列补全到
对节点标号:
稍加观察可以发现,每个位置
如果两个编号的 LCA 刚好是它们的父亲,那么这两个编号除以
同理,如果是第
每一位是否相同,刚好可以用异或判断。众所周知,异或运算“相同为
因此两个编号的 LCA 为
这时又会发现:如果每个节点都开一个 vector,由于空间限制,下标都要整体减去一个
但每一层的数组互不相交,并起来刚好等于全集,所以不如直接按层记录所有节点的前缀和、后缀和拼接后的结果。这样既不需要偏移下标,还能减少 vector 带来的常数。
代码如下:
int s[logn][maxn], a[maxn], lg[maxn], n;
void build(int l, int r, int dep) {
if (l == r) return;
int mid = (l + r) >> 1;
s[dep][mid] = a[mid];
for (int i = mid - 1; i >= l; i--) s[dep][i] = merge(a[i], s[dep][i + 1]);
s[dep][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) s[dep][i] = merge(s[dep][i - 1], a[i]);
build(l, mid, dep + 1), build(mid + 1, r, dep + 1);
}
int qry(int l, int r) {
int p = lg[(l + n - 1) >> (lg[(l + n - 1) ^ (r + n - 1)] + 1)] + 1;
return merge(s[p][l], s[p][r]);
}
猫树分治
正式考试中一般不会直接考猫树,通常考查的是猫树分治这一思想,虽然两者差别并不大。
所谓猫树分治,就是先将所有询问离线下来,在询问上分治,然后借用猫树的思想求解每个询问。
具体而言,每次递归时记录一个数组区间
在查询区间中,把所有完全位于
对于所有跨过
代码如下:
void solve(int l, int r, int ql, int qr) {
if (l == r) {
for (int i = ql; i <= qr; i++) ans[q[i].id] = a[l];
return;
}
int mid = (l + r) >> 1;
s[mid] = a[mid];
for (int i = mid - 1; i >= l; i--) s[i] = merge(a[i], s[i + 1]);
b[mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) b[i] = merge(b[i - 1], a[i]);
for (int i = ql; i <= qr; i++) tmp[i] = q[i];
int cntl = ql, cntr = qr;
for (int i = ql; i <= qr; i++) {
if (tmp[i].r <= mid) q[cntl++] = tmp[i];
else if (tmp[i].l > mid) q[cntr--] = tmp[i];
else ans[tmp[i].id] = merge(s[tmp[i].l], b[tmp[i].r]);
}
solve(l, mid, ql, cntl - 1);
solve(mid + 1, r, cntr + 1, qr);
}
猫树是什么复杂度,猫树分治就是什么复杂度。因此不少题目的猫树分治做法都可以转化为猫树,并且可以由离线变为在线。
为书写方便,下面例题代码均采用猫树分治做法,因为题目没有强制在线;想看猫树写法的读者可以自行尝试,从猫树分治转化到猫树理应是简单的。
例题
P11265 【模板】静态区间半群查询
题意:给定若干
模板题。
代码如下:
struct mat {
int a[2][2];
mat() { memset(a, 0x3f, sizeof(a)); }
mat operator * (const mat &oth) const {
mat res;
for (int i = 0; i < 2; i++)
for (int k = 0; k < 2; k++)
for (int j = 0; j < 2; j++)
res.a[i][j] = min(res.a[i][j], a[i][k] + oth.a[k][j]);
return res;
}
int operator ^ (const mat &oth) const {
int res = 0;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
res += a[i][j] ^ oth.a[i][j];
return res;
}
} kv, a[maxn], s[maxn], b[maxn];
int ans[maxn];
struct node {
int l, r, id;
} q[maxn], tmp[maxn];
void solve(int l, int r, int ql, int qr) {
if (ql > qr) return;
if (l == r) {
for (int i = ql; i <= qr; i++) ans[q[i].id] = a[l] ^ kv;
return;
}
int mid = (l + r) >> 1;
s[mid] = a[mid];
for (int i = mid - 1; i >= l; i--) s[i] = a[i] * s[i + 1];
b[mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) b[i] = b[i - 1] * a[i];
for (int i = ql; i <= qr; i++) tmp[i] = q[i];
int cntl = ql, cntr = qr;
for (int i = ql; i <= qr; i++) {
if (tmp[i].r <= mid) q[cntl++] = tmp[i];
else if (tmp[i].l > mid) q[cntr--] = tmp[i];
else ans[tmp[i].id] = s[tmp[i].l] * b[tmp[i].r] ^ kv;
}
solve(l, mid, ql, cntl - 1);
solve(mid + 1, r, cntr + 1, qr);
}
P6240 好吃的题目
题意:给定
注意到背包是
但实际上并不需要真正合并,只需要计算
即可,复杂度降到
另外,空间只有 125 MB,不要 #define int long long(
代码如下:
int w[maxn], v[maxn], b[maxn][250], s[maxn][250], ans[maxm];
struct node {
int l, r, t, id;
} q[maxm], tmp[maxm];
void solve(int l, int r, int ql, int qr) {
if (l == r) {
for (int i = ql; i <= qr; i++) ans[q[i].id] = (w[l] <= q[i].t ? v[l] : 0);
return;
}
int mid = (l + r) >> 1;
for (int i = 0; i < w[mid]; i++) s[mid][i] = 0;
for (int i = w[mid]; i <= 200; i++) s[mid][i] = v[mid];
for (int i = mid - 1; i >= l; i--) {
for (int j = 0; j < min(w[i], 201); j++) s[i][j] = s[i + 1][j];
for (int j = w[i]; j <= 200; j++) s[i][j] = max(s[i + 1][j], s[i + 1][j - w[i]] + v[i]);
}
for (int i = 0; i < w[mid + 1]; i++) b[mid + 1][i] = 0;
for (int i = w[mid + 1]; i <= 200; i++) b[mid + 1][i] = v[mid + 1];
for (int i = mid + 2; i <= r; i++) {
for (int j = 0; j < min(w[i], 201); j++) b[i][j] = b[i - 1][j];
for (int j = w[i]; j <= 200; j++) b[i][j] = max(b[i - 1][j], b[i - 1][j - w[i]] + v[i]);
}
for (int i = ql; i <= qr; i++) tmp[i] = q[i];
int cntl = ql, cntr = qr;
for (int i = ql; i <= qr; i++) {
if (tmp[i].r <= mid) q[cntl++] = tmp[i];
else if (tmp[i].l > mid) q[cntr--] = tmp[i];
else for (int j = 0; j <= tmp[i].t; j++) ans[tmp[i].id] = max(ans[tmp[i].id], s[tmp[i].l][j] + b[tmp[i].r][tmp[i].t - j]);
}
solve(l, mid, ql, cntl - 1);
solve(mid + 1, r, cntr + 1, qr);
}
P6009 [USACO20JAN] Non-Decreasing Subsequences P
题意:给定
简单 dp。设
理论上可以去掉
以
- 不选
a_i 的贡献:S_{i+1,j} 。 - 只选
a_i 的贡献:1 。 - 选
a_i 的贡献:需要再记录一个t_{j,k} ,表示在[i+1,mid] 中起点数值为j 、终点数值为k 的不下降子序列数,那么贡献为\sum_{k=a_i}^{j}t_{k,j} 。