DDP 和 GBBST

动态 dp，全局平衡二叉树。

动态 dp 入门

给道入门题。

题目：DTOJ #4579. Hello 2019

一个串是好的，当且仅当其包含子序列 \(9102\) 且不包含子序列 \(8102\). (子序列不一定连续)

有个数字串 \(S\)，每次询问一个区间 \((l,r)\)，求至少从串中删掉多少个字符，方能使子串 \(S(l,r)\) 是好的。

\(|S| \le 2\times 10^5\) | \(q\le 2\times 10^5\)。

题解：首先 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}\) 的时候是右子树乘左子树即可。

几个要点：

扩展 \(f_{u,1}\) 的定义：\(u\) 选的答案 \(\to\) \(u\) 选或不选的答案。
把除重儿子外的东西打包到 \(g_u\) 考虑。
来自P4719 最高赞题解：每条重链的链尾都是叶子节点，且只有叶子节点没有重儿子。这为动态规划的初始状态和转移方式做了保障。

提交记录

全局平衡二叉树

lxl：Global Biased Tree（GBT）

Yang Zhe：Global Balanced BST（GBBST）

洛谷 P4751 【模板】"动态DP"&动态树分治（加强版）

数据范围已经不允许 \(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 解法的一些研究

提交记录（无 IO 优化）

关于步骤：

树链剖分。
找出连接根节点的重链，对这条重链建立二叉搜索树，然后对连接这条重链的其他重链递归建立。
一棵二叉搜索树根节点要维护这棵二叉树的所有矩阵乘积。
修改 \(a_u \gets x\)：
1. 找到 \(u\) 所对应的平衡/线段树节点。
2. 修改 \(a_u\) 对应的矩阵。
3. 暴力往上跳，每次都 push_up。
4. 到根了，查看这棵平衡/线段树所对应的重链，找到链头的父亲，记作新的 \(u\)，没父亲就可以退出了。
5. 回到步骤 4.2。

关于实现：

上文有说是对每条重链依照带权中点二分建立一棵平衡树，这样是对的，但是有一些其他的实现方式。比如大部分博客会把轻儿子向父亲的平衡/线段树节点连一条虚边。
所谓虚边：因为它父亲所在的重链自己构成了一棵二叉树，其父亲无法变成多叉树，指向轻儿子，但是轻儿子可以指向父亲。即虚边，有认父不认子的特点。推荐这样的实现方式，这样在修改的时候就可以从 \(u\) 节点跳直接到顶，省去不少麻烦。详细见代码。

Code

// 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;
}

~~我能水一篇题解吗~~

DDP 和 GBBST

DDP 和 GBBST

动态 dp 入门

动态树分治入门

全局平衡二叉树

Code

推荐阅读