一类限制转化方法

1. 如果 \(\forall x\)，满足条件 \(A(x)\) 成立，即全局限制

2. \(\forall x,T=\{y|y\prec x\}=\emptyset,A(x)=1\)，即边界节点必成立。

3. 若 \(\forall x,\exists T_x\)，使得 \(\forall y\in T_x,y\prec x,A(y)\land B(x,y)\implies A(x)\) ，即条件可以转移

则等价于限制 \(\forall x,y\prec T_x,B(x,y)\) 成立，即使得转移成立即可。

证明：数学归纳证明显然，也可以感性理解。

例一：对于序列的每个节点，其后缀节点严格比他大，那么这是一个单调递增的序列：

证明：

1. \(\forall x,A(x):=\forall y>x,a_y>a_x\)

2. 对于 \(x=n\)，我们将其视作成立。

3. \(T_x:=\{x+1\},B(x,y):=a_x<a_y\)，则 \(A(x+1)\land B(x,x+1)\implies A(x)\)

所以原命题成立。

例二：对于一棵树，要求满足从每一个关键点走到根节点各一次，等价于要使得从每个点向上的边的次数等于这个点的子树中的关键点的数量。（即2024.11.7T3 string的重要引理）

首先 \(A(x):=x\) 子树中关键点到点 \(x\) 恰好走 \(x\) 的子树中关键点的个数次。

1. 则原题的充要条件为 \(\forall x,A(x)=1\)。证明是容易的。

2. \(\forall leaf(x)=1,A(x)\)显然成立。

3. \(T_x:=\{y|y\in son(x)\},B(x,y):=\)经过边 \((x,y)\) 的次数等于子树中关键的的次数，则 \(\forall y\in T_x,A(y)\land B(x,y)\implies A(x)\)

所以原命题成立。

该题的启示在于要找到一个合适的 \(A(x)\)，使得其转化为 \(\forall x,A(x)\)，成立问题。

例三：对于你需要构造一个序列\(\{b\}\)，使得这个序列的后缀数组等于原数组。（即2024.11.15T4 飒妃客厮 · 啊瑞）

解法：\(A(x,y)\) 表示以 \(x\) 开头的缀与以 \(y\) 开头的后缀的大小关系与给定的后缀数组的大小关系相同。

1. 要求 \(\forall x,y,A(x,y)=1\)

2. \(\forall x,A(x,n)\) 显然成立。

3. \(T_{x,y}=\{(x+1,y+1)\},B(x,y)=b_x<b_y\lor (rk_x\ne n\land rk_y\ne n\land rk_{x+1}<rk_{y+1}\land b_x=b_y)\)，则 \(A(x+1,y+1)\implies B(x,y)\)。

所以等价于 \(\forall x,y,B(x,y)\) 成立。

1. \(\forall A'(x):=\forall y>x,B(x,y)=1\)。

2. \(T_x=\{x+1\},B'(x,y)=B(x,y)\)，则 \(A(x+1)\land B(x,x+1)\implies A(x)\)

所以只需要 \(\forall x,B(x,x+1)\) 成立即可。