ddp 和 gbbst 口胡报告
lingfunny
·
·
题解
动态 dp 入门
给道入门题。
题目：DTOJ #4579. Hello 2019
一个串是好的，当且仅当其包含子序列 9102 且不包含子序列 8102. (子序列不一定连续)
有个数字串 S，每次询问一个区间 (l,r)，求至少从串中删掉多少个字符，方能使子串 S(l,r) 是好的。
题解：首先 reverse，然后记一个 $f_{i,0/1/2/3/4}$，表示恰好匹配 $0/1/2/3/4$ 个要删几个字符，然后用 $5\times 5$ 的矩阵转移，每次把 $[l,r]$ 内的矩阵乘起来。详细的建议自己推。
## 动态树分治入门
题目：洛谷 P4719 【模板】"动态 DP"&动态树分治
先写出一般最大权独立集式子：
$$
\begin{aligned}
f_{u,0} =& \sum_{v}\max(f_{v,0}, f_{v,1})\\
f_{u,1} =& w_u+\sum_{v} f_{v,0}
\end{aligned}
$$
其中 $f_{u,0/1}$ 表示 $u$ 不选/选的答案。
然后对于整棵树进行树剖，分开记重儿子和轻儿子的答案。
$g_{u,0}$：$u$ 的所有轻儿子全不选的总和加上 $w_u$。
$g_{u,1}$：$u$ 的所有轻儿子选或不选的最大值总和。
$f_{u,0}$：$u$ 不选的答案。
$f_{u,1}$：$u$ 选或不选的答案。
记 $v$ 为重儿子，有：
$$
\begin{aligned}
f_{u,0} =& f_{v,1} + g_{u, 1}\\
f_{u,1} =& \max(f_{v,1} + g_{u, 1}, f_{v,0} + g_{u,0})
\end{aligned}
$$
然后可以把 $f_u$、$g_u$ 和 $f_v$ 写成矩阵，要点是 $f_u$ 和 $f_v$ 长得一样，$g_u$ 只和 $u$ 有关：
$$
\begin{bmatrix}
f_{u, 0} & f_{u, 1}
\end{bmatrix}
=
\begin{bmatrix}
f_{v, 0} & f_{v,1}
\end{bmatrix}
\times
\begin{bmatrix}
-\infty & g_{u,0}\\
g_{u, 1} & g_{u,1}
\end{bmatrix}
$$
当然这里矩阵乘法的定义是 $(+, \max)$。
这样一个**节点**到**重链顶端**的答案就是 $\begin{bmatrix}0 & 0\end{bmatrix}$ 和这条链的叶结点从底到顶的一堆矩阵相乘。
此时如果修改一个节点，只需改的它的 $g_u$ 矩阵。
然后跑到重链顶端，求出新矩阵，对链顶父亲的 $g_u$ 修改一下，然后继续跑。
实现上需要注意矩阵是从链底端乘到链顶端，倒序。
似乎只需要线段树上 $\texttt{query}$ 的时候是右子树乘左子树即可。
几个要点：
1. 扩展 $f_{u,1}$ 的定义：$u$ 选的答案 $\to$ $u$ 选或不选的答案。
2. 把除重儿子外的东西打包到 $g_u$ 考虑。
3. 来自[P4719 最高赞题解](https://www.luogu.com.cn/blog/Tweetuzki/solution-p4179)：每条重链的链尾都是叶子节点，且只有叶子节点没有重儿子。这为动态规划的初始状态和转移方式做了保障。
[提交记录](https://www.luogu.com.cn/record/76042967)
## 全局平衡二叉树
全局平衡二叉树
lxl：**G**lobal **B**iased **T**ree（**GBT**）
Yang Zhe：**G**lobal **B**alanced **BST**（**GBBST**）
[洛谷 P4751 【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751)
数据范围已经不允许 $O(\log^2 n)$ 的做法了。
注意到上面那个做法的劣势在于：每次树剖查询的是若干条重链，而就算一条链的长度 $l=1$，单次查询重链复杂度都是 $O(\log n)$，因为是开一棵线段树维护所有节点的矩阵。总的合并复杂度就是 $O(\log^2 n)$。
考虑修改一下，对每条重链单独用一个形态不变的二叉树维护，网络上大部分博客都是非 leafy 结构，类似平衡树。但写成 leafy 的线段树也不会错。
> leafy 两倍常数 —— rsy
问题在于如果还是按照一般的线段树建树，每次找中点，$O(\log n)\sum O(\log l)$ 仍可以卡到 $O(\log^2 n)$。
考虑记：
$$
\mathrm{Lsize}(u)=1+\sum_{v\in \mathrm{LightSon}(u)} \mathrm{size}_v
$$
即所有轻儿子 $\mathrm{size}$ 之和加上自己。
这时候，如果在重链上按照 $\mathrm{Lsize}$ 为权值，找到带权中点，然后递归到左右建（平衡/线段）树来维护信息，均摊下来修改的复杂度就是 $O(\log n)$ 的。
为什么？不知道。难道你知道为什么 Splay 均摊是 $O(q\log n )$ 的吗？
详细证明可见 [Yang Zhe - QTREE 解法的一些研究](https://wenku.baidu.com/view/75906f160b4e767f5acfcedb)
[提交记录](https://www.luogu.com.cn/record/76069612)（无 IO 优化）
关于步骤：
1. 树链剖分。
2. 找出连接根节点的重链，对**这条重链**建立二叉搜索树，然后对连接这条重链的其他重链**递归**建立。
3. 一棵二叉搜索树根节点要维护这棵二叉树的**所有矩阵乘积**。
4. 修改 $a_u \gets x$：
1. 找到 $u$ 所对应的平衡/线段树节点。
2. 修改 $a_u$ 对应的矩阵。
3. 暴力往上跳，每次都 push_up。
4. 到根了，查看这棵平衡/线段树**所对应的重链**，找到链头的父亲，记作新的 $u$，没父亲就可以退出了。
5. 回到步骤 4.2。
关于实现：
1. 上文有说是对每条重链依照带权中点二分建立一棵平衡树，**这样是对的**，但是有一些其他的实现方式。比如大部分博客会把轻儿子向父亲的平衡/线段树节点连一条**虚边**。
2. 所谓**虚边**：因为它父亲所在的重链自己构成了一棵二叉树，其父亲无法变成多叉树，指向轻儿子，但是轻儿子可以指向父亲。即**虚边**，有**认父不认子**的特点。推荐这样的实现方式，这样在修改的时候就可以从 $u$ 节点跳直接到顶，省去不少麻烦。详细见代码。
### Code
```cpp
// Problem: P4751 【模板】"动态DP"&动态树分治（加强版）
// From: Luogu
// URL: https://www.luogu.com.cn/problem/P4751
// Time: 2022-05-19 21:21
// Author: lingfunny
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn = 1e6+10, inf = 1e9;
int n, m, lst, a[mxn], rt, f[mxn][2], g[mxn][2];
vector <int> G[mxn];
struct mat {
static const int V = 2;
int a[V][V];
mat(int a00 = 0, int a01 = -inf, int a10 = -inf, int a11 = 0) { a[0][0] = a00, a[0][1] = a01, a[1][0] = a10, a[1][1] = a11; }
inline mat operator * (const mat &rhs) const {
mat res;
for(int i = 0; i < V; ++i) for(int j = 0; j < V; ++j) {
res.a[i][j] = -inf;
for(int k = 0; k < V; ++k) res.a[i][j] = max(res.a[i][j], a[i][k] + rhs.a[k][j]);
}
return res;
}
inline void show() {
for(int i = 0; i < V; ++i) for(int j = 0; j < V; ++j) printf("%d%c", a[i][j], " \n"[j==V-1]);
}
} gm[mxn];
struct node { int lc, rc, anc; mat u, s; } nd[mxn];
inline void psup(int u) {
node &o = nd[u];
o.s = nd[o.rc].s * o.u * nd[o.lc].s; // 反着乘，原因见上文 P4719
}
int sz[mxn], lsz[mxn], dep[mxn], fa[mxn], son[mxn], top[mxn], End[mxn], dfn[mxn], mp[mxn], dfc;
// lsz[u]: Lsize[u]
// top/End: 重链顶/底
// mp: mp[dfn[u]] = u
void dfs(int u, int f) {
lsz[u] = sz[u] = 1, dep[u] = dep[f] + 1, fa[u] = f;
for(int v: G[u]) if(v != f) {
dfs(v, u), sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
lsz[u] = sz[u] - sz[son[u]];
}
void dfs2(int u) {
End[u] = mp[dfn[u] = ++dfc] = u; g[u][0] = a[u];
if(son[u]) top[son[u]] = top[u], dfs2(son[u]), End[u] = End[son[u]];
for(int v: G[u]) if(v != fa[u] && v != son[u]) top[v] = v, dfs2(v), g[u][0] += f[v][0], g[u][1] += f[v][1];
f[u][0] = f[son[u]][1] + g[u][1];
f[u][1] = max(f[u][0], f[son[u]][0] + g[u][0]);
gm[u] = mat(-inf, g[u][0], g[u][1], g[u][1]);
}
int sbuild(int L, int R) {
if(L > R) return 0;
LL sum = 0, qsum = 0;
for(int i = L; i <= R; ++i) sum += lsz[mp[i]];
for(int i = L, o; i <= R; ++i) {
qsum += lsz[mp[i]];
if(qsum * 2 > sum) {
o = mp[i];
node &u = nd[o];
u.u = gm[o];
u.lc = sbuild(L, i-1), nd[u.lc].anc = o;
u.rc = sbuild(i+1, R), nd[u.rc].anc = o;
psup(o);
return o;
}
}
return -114514;
}
int build(int Tp) {
int Ed = End[Tp], X = sbuild(dfn[Tp], dfn[Ed]);
for(int i = dfn[Tp]; i <= dfn[Ed]; ++i) {
const int &u = mp[i];
for(int v: G[u]) if(v != son[u] && v != fa[u]) nd[build(v)].anc = u;
}
return X;
}
inline void modify(int u, int x) {
gm[u].a[0][1] += x - a[u]; a[u] = x;
nd[u].u = gm[u];
while(u) {
int F = nd[u].anc;
if(nd[F].lc != u && nd[F].rc != u && F) { // 如果当前节点到父亲的边是虚边
mat bef = nd[u].s;
psup(u);
mat aft = nd[u].s;
int _f0 = max(bef.a[0][0], bef.a[1][0]), _f1 = max(bef.a[0][1], bef.a[1][1]),
f0 = max(aft.a[0][0], aft.a[1][0]), f1 = max(aft.a[0][1], aft.a[1][1]);
mat &r = nd[F].u;
r.a[0][1] += f0 - _f0;
r.a[1][0] += f1 - _f1, r.a[1][1] += f1 - _f1;
gm[F] = r;
} else psup(u);
u = F;
}
}
signed main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", a+i);
for(int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
dfs(1, 0), top[1] = 1, dfs2(1), rt = build(1);
while(m--) {
int x, y; scanf("%d%d", &x, &y); x ^= lst;
modify(x, y);
printf("%d\n", lst=max(nd[rt].s.a[0][1], nd[rt].s.a[1][1]));
}
return 0;
}
```
~~我能水一篇题解吗~~