动态规划基础：线性 DP、背包模型与区间 DP

一、线性 DP 与状态定义转换

在动态规划中，状态定义的视角往往决定了算法的复杂度上限。遇到 $O(n^2)$ 必然超时的瓶颈时，第一反应必须是“改变状态的维度或物理含义”。

1. LIS 的贪心二分优化与 Dilworth 定理

初始痛点：普通 DP 定义 $f[i]$ 为“以第 $i$ 个元素结尾的最长上升子序列长度”。这种定义下，每次寻找转移点都需要遍历 $1 \dots i-1$ ，复杂度死死卡在 $O(n^2)$ 。

降维推导（潜力贪心法）：

我们不再记录“以谁结尾”，而是记录“达到特定长度时，最小的结尾元素是多少”。

维护一个单调递增的数组 low，low[len] 表示长度为 $len$ 的最长上升子序列的末尾元素的最小值。

物理意义：在同样长度的子序列中，末尾元素越小，它后续能接上新数字的“潜力”就越大。
状态转移策略：遍历原数组，遇到比 low 数组末尾更大的数，说明突破了当前最大长度，直接追加；否则，它虽然不能增加总长度，但能“优化”某个已有长度的末尾潜力——用二分查找替换掉 low 数组中第一个大于等于它的数。

场景微操演练：序列 [3, 1, 4, 2, 5]

读入 3：low = [3]，当前最长长度 1。
读入 1：1 比 3 小，无法追加。二分找到 3 并替换。low = [1]。（物理意义：长度为 1 的序列，以 1 结尾比以 3 结尾更有潜力）。
读入 4：4 > 1，潜力爆发，直接追加。low = [1, 4]，当前最长长度 2。
读入 2：替换 4。low = [1, 2]。（物理意义：找到了更优的长度为 2 的序列 [1, 2]，比 [1, 4] 更好接数字）。
读入 5：5 > 2，追加。low = [1, 2, 5]，最终最长长度 3。

考场拔高：Dilworth 定理

提高组极少直白地考 LIS，通常披着“最少划分”的外衣（如经典的“导弹拦截”问题：求最少需要几套系统才能拦截所有导弹）。

定理核心：把一个序列剖分成若干个单调不升子序列的最小剖分个数，绝对等于该序列的最长上升子序列 (LIS) 的长度。直接套用本模型即可 $O(n \log n)$ 秒杀。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int a[N],low[N];

int calc_lis(int n){
	int len=1;
	low[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>low[len]){
			low[++len]=a[i]; // 潜力突破，增加长度
		}else{
			*lower_bound(low+1,low+len+1,a[i])=a[i]; // 潜力优化，替换掉第一个大于等于它的数
		}
	}
	return len;
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<calc_lis(n)<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

LIS：low 数组记录最小结尾

二、基础背包的推导与空间依赖

核心变量全局约定：

在接下来的所有模型和代码中，我们统一物理量标准，这也是提高组考场上的标准缩写：

w[i] (Weight)：表示第 $i$ 种物品的重量（物理意义：我们需要付出的代价、消耗的背包容量）。
v[i] (Value)：表示第 $i$ 种物品的价值（物理意义：我们得到的收益，越大越好）。
m：背包的总容量限制。

背包 DP：循环顺序决定能否重复选

三、01 背包：状态转移的本源与“时间差”陷阱

场景：有 $n$ 种物品，每种物品绝对只能选 1 次或不选。

1. 二维状态的绝对安全

在最原始的思维中，我们需要两个维度来标记状态：

状态定义： $f[i][j]$ 表示“在只考虑前 $i$ 种物品的情况下，放入容量为 $j$ 的背包中所能获得的最大收益”。
转移方程：

$f[i][j] = \max(f[i-1][j], f[i-1][j-w[i]] + v[i])$
物理推导：面对第 $i$ 件物品，我们只有两个选择：
1. 不选：那收益就完全继承前 $i-1$ 件物品在容量 $j$ 下的最优解，即 $f[i-1][j]$ 。
2. 选：前提是容量够（ $j \ge w[i]$ ）。我们必须回到前 $i-1$ 件物品、且容量为 $j-w[i]$ 的平行宇宙中寻找最优解，加上当前物品的收益 $v[i]$ 。

2. 一维降维与内层循环的生死抉择

二维数组 $O(nm)$ 的空间在极大数据下必爆内存（MLE）。观察方程发现，第 $i$ 层的状态，仅仅依赖于第 $i-1$ 层的状态。我们完全可以把第一维抹掉，只用一个一维数组 $f[j]$ 来滚动更新。

降维后的致命问题：

方程变成了 $f[j] = \max(f[j], f[j-w[i]] + v[i])$ 。

当我们在计算当前物品的 $f[j]$ 时，所需的 $f[j-w[i]]$ 必须是上一层（即没选过当前物品）的数据。

破局方案：倒序遍历容量

如果从小到大正序遍历， $f[j-w[i]]$ 会先于 $f[j]$ 被计算。这就导致计算 $f[j]$ 时，用的是已经被当前物品更新过的新数据——等同于一件物品被选了两次！

铁律：必须让容量 $j$ 从 $m$ 倒推到 $w[i]$ 。这样每次读取左侧的 $f[j-w[i]]$ 时，它都还是上一个循环留下来的“干净数据”。

下面是核心函数片段，不含读入与 main。本篇背包片段沿用前文的头文件、命名空间和 long long 设置。接入自己的程序时，先读好 w/v，把 f[0..m] 初始化为 0，再调用 pack_01(n,m)。

const int N=1005,M=200005;
int w[N],v[N],f[M];

void pack_01(int n,int m){
	for(int i=1;i<=n;i++){
		// 铁律：01 背包必须倒序遍历容量
		for(int j=m;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
}

四、完全背包：重复选取与正序更新

场景：每种物品可以无限次选取，只要背包装得下。

1. 物理意义的翻转（为什么正序？）

在 01 背包中，我们为了防止物品被重复选取而使用了倒序。但在完全背包中，“重复选取”正是我们需要的！

因此，完全背包的容量 $j$ 必须正序遍历（从小到大）。当计算 $f[j]$ 时，如果它依赖的 $f[j-w[i]]$ 已经被当前物品更新过，恰好说明：“在已经装了一件当前物品的基础上，空间如果还够，我可以继续装这件物品”。

2. 真题拆解：P17012 《条形蛋糕》

这道题是披着“分割”外衣的纯正完全背包模板题。我们要教学生学会“翻译”题目：

蛋糕总长度 $n$ $\rightarrow$ 背包的总容量 m。
切出的蛋糕块长度 $i$ $\rightarrow$ 第 $i$ 种物品的重量（消耗量）w[i]。
蛋糕块对应的价格 $p_i$ $\rightarrow$ 第 $i$ 种物品的价值（收益）v[i]。
同一长度可以切多块 $\rightarrow$ 物品可以无限次选取 $\rightarrow$ 完全背包（内层容量正序）。

样例 1 状态微操推演 ( $n=4$ , 价格分别为 $1, 5, 8, 9$ )：

当枚举到长度为 2 的蛋糕块 ( $w[2]=2, v[2]=5$ )，正序更新容量：

容量 $j=2$ ： $f[2] = \max(f[2], f[0]+5) = 5$ （切 1 块长度 2）
容量 $j=3$ ： $f[3] = \max(f[3], f[1]+5) = 6$ （1 块长度 1 + 1 块长度 2）
容量 $j=4$ ： $f[4] = \max(f[4], f[2]+5) = 10$ （核心：这里 $f[4]$ 利用了刚刚在本次循环更新的 $f[2]$ ，等价于切了 2 块长度 2 的蛋糕，收益 $5+5=10$ ，大于原封不动卖的 9 块钱）。

参考代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,M=1005;
int w[N],v[N],f[M];

void solve_cake(){
	int n;
	cin>>n; // 输入总长度，既是物品种类数，也是背包总容量
	for(int i=1;i<=n;i++){
		w[i]=i;       // 重量 = 蛋糕块的长度
		cin>>v[i];    // 价值 = 蛋糕块的销售价格
	}
	
	// 完全背包核心：正序遍历容量
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=n;j++){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[n]<<'\n'; // 直接输出最大收益
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve_cake();
    return 0;
}

多重背包：二进制拆分

五、多重背包：时间复杂度的极限压榨（二进制拆分）

场景：物品有具体的数量限制 $c_i$ 。

1. 为什么不能暴力展开？

如果一件物品有 1000 件，直接把它复制成 1000 件独立的 01 背包物品，时间复杂度 $O(n \times c \times m)$ 会直接超时。

2. 二进制拆分的数学魔法

任何十进制数字，都可以用 $2^0, 2^1, 2^2 \dots$ 来完美凑出。

举例证明：假设有 $13$ 个苹果。我们不把它拆成 13 个“1”，而是打包成四个箱子：装 1 个、2 个、4 个、6 个（最后的补数）。

用 1、2、4 的箱子，我们可以通过选与不选，无缝拼凑出 $0 \dots 7$ 之间的任何数目。
在这个基础上，加上那个装了 6 个苹果的补数箱，我们就能无缝拼凑出 $6 \dots 13$ 之间的任何数目。

结论：把 $c_i$ 件物品打包成 $\log c_i$ 件具有新重量和新收益的大包裹，对这些大包裹跑一遍 01 背包，复杂度瞬间降维至 $O(nm \log c_i)$

下面是核心函数片段，不含 main。先读 n,m，把 f[0..m] 初始化为 0；调用 pack_multi(n,m) 时，函数会继续读入每种物品的重量、价值和件数。N 要能容纳拆分后的总包数。

const int N=20005,M=100005;
int w_new[N],v_new[N],f[M];

void pack_multi(int n,int m){
	int cnt=0;
	for(int i=1;i<=n;i++){
		int w,v,c; // w：重量，v：价值，c：最多可选件数
		cin>>w>>v>>c;
		
		// 1. 二进制核心打包
		for(int k=1;k<=c;k<<=1){
			cnt++;
			w_new[cnt]=w*k;
			v_new[cnt]=v*k;
			c-=k; // 扣除已打包的数量
		}
		// 2. 将零头作为一个独立包裹
		if(c>0){
			cnt++;
			w_new[cnt]=w*c;
			v_new[cnt]=v*c;
		}
	}
	
	// 3. 对这 cnt 个新物品，跑标准的 01 背包 (倒序)
	for(int i=1;i<=cnt;i++){
		for(int j=m;j>=w_new[i];j--){
			f[j]=max(f[j],f[j-w_new[i]]+v_new[i]);
		}
	}
}

分组背包：组内物品平行竞争

六、分组背包：树形背包的绝对基石

场景：物品被划分为 $n$ 组，每组内最多只能选择一件物品。

1. 绝对互斥的物理实现

要保证同组内只能选一件，就必须让这组内的所有物品在同一个容量状态下互相厮杀，赢的那个才能更新状态。

死亡陷阱：如果把容量遍历放在最内层，相当于先决定了选物品 A 占了空间，然后在此空间基础上又让物品 B 去更新更大的空间，导致同组物品共存！

循环结构铁律（必须刻在肌肉记忆里）：

外层：枚举当前是哪一组。
中层：枚举背包容量 $j$ （必须倒序，本质还是 01 背包限制只能选一次）。
内层：枚举组内的所有物品 $k$ ，让它们平行竞争当前容量 $j$ 的归属权。

下面是核心函数片段，不含读入与 main。先读好每组的件数 c[i]、重量 w[i][k] 和价值 v[i][k]，把 f[0..m] 初始化为 0，再调用 pack_group(n,m)。

const int N=1005,M=1005;
int w[N][N],v[N][N],c[N],f[M];

void pack_group(int n,int m){
	// 铁律：组号 -> 容量倒序 -> 组内物品
	for(int i=1;i<=n;i++){ 
		for(int j=m;j>=0;j--){ 
			for(int k=1;k<=c[i];k++){ 
				if(j>=w[i][k]){
					// 在同组内不同物品间取最大值，覆盖原来的 f[j]
					f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
				}
			}
		}
	}
}

区间 DP：短区间先算与环形复制

七、区间 DP 与环形断链

区间 DP 专门打击“相邻元素合并/消除”类问题，核心特征是状态依赖于边界的收缩与分割。

1. 核心循环结构与拓扑顺序

痛点：大区间的状态 $f[i][j]$ 必须由切分点 $k$ 处的两个小区间 $f[i][k]$ 和 $f[k+1][j]$ 组合而成。如果单纯地先枚举左端点 $i$ ，再枚举右端点 $j$ ，在计算 $f[i][j]$ 时， $f[k+1][j]$ 可能根本还没被计算出来。

破局：必须优先保证所有短区间都被计算完毕。

三重循环顺序：枚举区间长度 -> 枚举左端点 -> 计算右端点 -> 枚举分割点。右端点直接由长度和左端点算出，不另开一重循环。

2. 环形问题的断链为倍技巧

痛点：当石子首尾相连成环时，跨越首尾的合并情况被线性的数组截断了。

降维打击：不要去写复杂的取模运算。直接将原数组复制一份接在尾部，长度变为 $2n$ 。这在物理上直接展开了所有的断链可能。跑完正常的线型区间 DP 后，只需在所有长度恰好为 $n$ 的区间中（即扫描所有的 $f[i][i+n-1]$ ）取最值即可。

前缀和优化：合并区间 $i \dots j$ 时，产生的代价通常是该区间内所有元素的和。利用预处理的前缀和 sum[j] - sum[i-1] 可实现 $O(1)$ 的代价查询。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
int a[N],sum[N],f[N][N],g[N][N];

void calc_interval(int n){
	// 1. 枚举区间长度 len (从 2 开始，长度 1 的代价为 0，已在初始化中完成)
	for(int len=2;len<=n;len++){
		// 2. 枚举左端点 i，注意边界是 2n - len + 1
		for(int i=1;i<=n*2-len+1;i++){
			// 3. 计算右端点 j
			int j=i+len-1;
			// 4. 枚举分割点 k
			for(int k=i;k<j;k++){
				int cost=sum[j]-sum[i-1]; // O(1) 获取合并代价
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+cost);
				g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+cost);
			}
		}
	}
}

void solve(){
	int n;
	cin>>n;
	// 核心技巧：断链为倍，数据复制
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=n*2;i++) sum[i]=sum[i-1]+a[i];
	
	memset(f,0x3f,sizeof f);
	memset(g,0,sizeof g);
	for(int i=1;i<=n*2;i++) f[i][i]=0,g[i][i]=0;
	
	calc_interval(n);
	
	int minx=1e18,maxx=0;
	// 在所有真实长度为 n 的窗口中寻找全局最优解
	for(int i=1;i<=n;i++){
		minx=min(minx,f[i][i+n-1]);
		maxx=max(maxx,g[i][i+n-1]);
	}
	cout<<minx<<'\n'<<maxx<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

八、双串线性 DP 状态对比：LCS 与编辑距离（选学）

先修知识：已熟练掌握基础的一维线性 DP 与二维数组状态映射。

场景：同时给你两个字符串 $A$ 和 $B$ （如求最长公共子序列，或将 $A$ 变成 $B$ 的最少操作次数），此时一维状态肯定不够用了。

物理视角：我们需要让两个指针 $i$ 和 $j$ 分别在 $A$ 和 $B$ 上滑动。状态 $f[i][j]$ 的物理意义通常是：“只看前缀 $A[1 \dots i]$ 和 $B[1 \dots j]$ ，我们能得到的最佳结果”。

1. LCS（最长公共子序列）的状态转移

问题：求 $A$ 和 $B$ 的最长公共部分（可以不连续）。

转移推导：考察末尾字符 $A[i]$ 和 $B[j]$ ：

如果相等（ $A[i] == B[j]$ ）：这是天赐良机，双双采纳！收益直接基于两者都短一截的状态 $+1$ 。
$f[i][j] = f[i-1][j-1] + 1$
如果不等（ $A[i] \neq B[j]$ ）：它们不可能同时出现在最后的公共子序列结尾。我们只能“抛弃”其中一个，去前面碰碰运气。要么抛弃 $A[i]$ ，要么抛弃 $B[j]$ ，取两者的最大值。
$f[i][j] = \max(f[i-1][j], f[i][j-1])$

2. 编辑距离（Edit Distance）的状态差别

问题：允许插入、删除、替换字符，把 $A$ 变成 $B$ 最少需要几步？

转移推导：同样考察末尾字符 $A[i]$ 和 $B[j]$ ：

如果相等（ $A[i] == B[j]$ ）：完美匹配，不需要任何操作。直接白嫖前缀的代价。
$f[i][j] = f[i-1][j-1]$
如果不等（ $A[i] \neq B[j]$ ）：遇到麻烦，我们要花 $1$ 步操作来强行抹平差异，有三种物理手段：
1. 替换：把 $A[i]$ 换成 $B[j]$ ，然后它们就匹配了，代价基于 $f[i-1][j-1]$ 。
2. 删除：把多余的 $A[i]$ 删掉，让 $A[1 \dots i-1]$ 继续去匹配 $B[1 \dots j]$ ，代价基于 $f[i-1][j]$ 。
3. 插入：在 $A$ 后面强行插入一个 $B[j]$ ，那么 $B[j]$ 就匹配上了，我们还需要让 $A[1 \dots i]$ 去匹配剩下的 $B[1 \dots j-1]$ ，代价基于 $f[i][j-1]$ 。
  $f[i][j] = \min(\{f[i-1][j-1], f[i-1][j], f[i][j-1]\}) + 1$

微操演练：把 $A=$ cat 变成 $B=$ cart 考察到 $A$ 的第 3 位 t 和 $B$ 的第 4 位 t，由于相等， $f[3][4] = f[2][3]$ （即 ca 变成 car 的代价）。而 ca 变成 car 的最优选择是插入 r，代价为 1。所以最终只需要 1 步。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int f[N][N];

void solve(){
	string a,b;
	cin>>a>>b;
	int n=a.length(), m=b.length();
	// 转换为 1-based 索引，避开边界越界
	a=" "+a; 
	b=" "+b;
	
	// 初始化：其中一个字符串为空时，代价就是不断删除或插入另一个字符串的长度
	for(int i=0;i<=n;i++) f[i][0]=i;
	for(int j=0;j<=m;j++) f[0][j]=j;
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]){
				f[i][j]=f[i-1][j-1]; // 完美继承
			}else{
				// 分别对应：替换、删除、插入
				f[i][j]=min({f[i-1][j-1], f[i-1][j], f[i][j-1]}) + 1;
			}
		}
	}
	cout<<f[n][m]<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

九、背包模型的进阶微操：初始化与方案数

很多同学只会背方程，一遇到“恰好装满”或“求方案数”的变种就立刻抓瞎。别急着重写整套循环：先调整最初的物理宇宙设定（初始化）；如果改求方案数，再把转移中的“取最大”换成“累加”。

1. “至多装 M” 与 “恰好装满 M”

痛点：平常写的背包都是“背包容量为 $M$ ，你可以装不满，求最大价值”。如果题目强制要求“必须严丝合缝把背包装满，否则算作失败”，该怎么办？

降维打击（利用极小值隔离不合法状态）：

至多装 M（常规情况）：初始化 f[0...m] = 0。
- 物理意义：一开始什么都没装的时候，无论你有多少容量的空闲背包，它的价值都是 0（合法的起始状态）。
恰好装满 M：初始化 f[0] = 0，其余 f[1...m] = -1e18（极小值）。
- 物理意义：一开始什么都没装的时候，只有“容量为 0 的背包”被恰好装满，价值是 0。其他容量 $1 \dots M$ 的背包在不装东西时，根本不满足“恰好装满”的要求，它们属于非法的平行宇宙。赋极小值是为了让它们在后续的 max 竞争中永远无法翻身，除非某次转移恰好能拼凑出它们的容量，将其从深渊中拉出来。

2. 求“恰好装满的方案数”

场景：不再求最大价值，而是问“把容量恰好装满有多少种不同的装法？”（例如经典的凑零钱问题）。

物理推导：

初始化改变：f[0] = 1，其余 f[1...m] = 0。（容量为 0 时有 1 种方案：什么都不选。其他容量初始为 0 种方案）。
运算符号改变：既然是求所有可能的总和，转移就不再是竞争（max），而是汇总（+）。
$f[j] = f[j] + f[j - w[i]]$
（物理意义：当前容量 $j$ 的总方案数，等于不选当前物品的方案数 $f[j]$ ，加上选当前物品时、前置容量 $j-w[i]$ 传导过来的方案数）。

容量循环方向仍跟着物品模型走：每种物品只能用一次就倒序；凑零钱这类可以重复用的就正序，别换成计数后把这条规矩忘了。

十、区间 DP 的路径记录：从断开位置恢复方案

痛点：区间 DP 跑完了，我们知道了最小代价，但题目经常会恶心一下：“请输出具体的合并步骤 / 括号的匹配方式”。我们该怎么把结果找回来？

1. 核心思想：留下路标

在计算 $f[i][j]$ 的时候，我们遍历了所有的分割点 $k$ ，找到了能让 $f[i][j]$ 取到最小值的那个最佳 $k$ 。我们不要算完就扔！专门开一个二维数组 path[i][j]，它的物理意义是：记录区间 $[i, j]$ 是在哪个点被劈开才得到最优解的。

关键代码插入点：

// 在枚举分割点 k 时顺手记录路标
if(f[i][k] + f[k+1][j] + cost < f[i][j]){
    f[i][j] = f[i][k] + f[k+1][j] + cost;
    path[i][j] = k; // 刻下这一刀砍在何处
}

2. 剥洋葱式递归输出

有了 path 数组，我们就拥有了一张寻宝图。从最外层的大区间 $[1, n]$ 开始，顺藤摸瓜向下剥洋葱。

物理过程：如果我们要知道区间 $[i, j]$ 是怎么合并的：

查表找到它的分割点 $k = path[i][j]$ 。
告诉左手：去把区间 $[i, k]$ 的合并步骤搞定。
告诉右手：去把区间 $[k+1, j]$ 的合并步骤搞定。
左右两边都搞定了，我们把它们两坨整体合在一起。

短模板：递归打印括号：

// 递归输出区间 [i, j] 的合并结构
void print_path(int i, int j){
	if(i == j){
		cout << "A" << i; // 剥到了最底层的单个元素
		return;
	}
	int k = path[i][j]; // 找到当年那一刀的位置
	cout << "(";
	print_path(i, k);       // 递归处理左半边
	cout << " * ";
	print_path(k + 1, j);   // 递归处理右半边
	cout << ")";
}

3. 环形题：先找最佳断口，再还原原编号

第七节把环复制成了长度为 $2n$ 的链，最佳窗口未必从 1 开始。先在全局补上 int path[N][N];，并用本节第一段的“比较并记录”代码替换原来的 f[i][j]=min(...) 更新；然后在所有长度为 $n$ 的窗口中记下最佳起点：

int st=1;
for(int i=2;i<=n;i++){
	if(f[i][i+n-1]<f[st][st+n-1]) st=i;
}
print_path(st,st+n-1);

打印叶子时，把 cout << "A" << i; 改为 cout << "A" << (i-1)%n+1;，就能将复制段的编号还原为原来的 1..n（让 print_path 能访问原长度 n）。例如 n=4、窗口从 3 开始，叶子编号应输出 3,4,1,2。这里记录的是最小代价方案；若还要恢复最大代价方案，应在更新 g 时另存一张分割点表。