找出每条边权值的可能的取值范围。

取值范围已经找出，接下来只需满足链上存在一条权值为 $z$ 的边。

首先找出每条边权值的可能的范围。要求 $x$ 到 $y$ 最大值为 $z$，即要求其上每一条边的权值小于等于 $z$，且至少有一个等于 $z$。

两个条件分开考虑：

• 要求每条边权小于等于（或大于等于）某个值，可以直接树剖线段树区间取 $\min$（$\max$）维护。随后得到取值范围。
• 要求至少有一个等于 $z$，发现每条边最多满足一个这样的条件，可以想到匹配。将每条边认为是一个点，向可能满足的条件连边。不难发现，每条边『可能满足的条件』数不超过 $2$，可以使用度为二的方法来做。

简单说一下二分图匹配，左侧度数均小于等于二的做法：度数为一时，将其所连的点自己连一个自环；度数为二时，将其两个相连的点间再连边。转化为给每条边定向，让每个点至少有一个入度。每个连通块若点数小于等于边数就有完美匹配，构造是容易的。

代码。

中序遍历，保证有解，其有非常优美的性质。

栈。

发现代码巨短无比，怀疑是杀交互库就去瞄了一眼，我错了，，直接看到一个栈。

首先有一个交互次数 $O(n \log n)$ 的做法（口胡的没写），大概就是设计一个递归函数，表示把某段区间里的树建出来。找根可以二分，前缀和整个区间的 $\gcd$ 从不同变成相同的那个点的 $S$ 就一定是它的 $\gcd$，因为保证有解。然后它是根，递归即可。

但是正解和这东西几乎无关。考虑按编号一个个加点，用一个栈维护当前树的最右链。

设栈顶为 $b$，新加的点为 $i$，可以直接查询 $i$ 是否在 $b$ 的子树里，方式大概是 $\operatorname{query}(b, b, b, i)$。如果返回真就在其子树内。此时，若 $b$ 已经有右孩子 $r$，那么 $S _ i | S _ r$，否则就可以证明它无解。证明大概是，首先因为 $S _ i \not| S _ r$ 且 $ S _ b | S _ r$，所以 $S _ i \ne S _ b$，同理得 $S _ r \ne S _ b$；又因为 $r$ 及其子树都在 $b$ 子树内而且无法逃脱，所以 $i$ 必然在 $b$ 子树里；然后因为 $r$ 原来在栈里但 $i$ 不能在 $r$ 子树里所以 $S _ r \not | S _ i$，所以在 $b$ 的右子树内有两个互不能为祖先关系的点，矛盾。

接着说做法。

• 如果 $b$ 没有右孩子，直接把 $i$ 接上去；
• 如果 $b$ 有右孩子 $r$，把 $r$ 接到 $i$ 的左孩子，把 $i$ 接到 $b$ 的右孩子；
• 如果找不到 $b$，设栈顶为 $p$，那么 $i$ 一定是 $p$ 的祖先，把 $p$ 接到 $i$ 的左孩子。

栈容易维护。

代码。

考虑快速计算连续选择的一段 $A$ 的权值。

考虑拆贡献。

考虑 dp。

首先考虑快速计算连续段的权值：对 $A$ 和 $B$ 复制无穷份做前缀和（环），记作 $a$ 和 $b$，则选择 $A$ 中 $[i, j]$，权值为 $a _ j - a _ {i - 1} - (b _ {j + k - 1} - b _ {j - 1})$。记 $c _ i = a _ {i - 1} - b _ {i - 2 + k}, d _ i = b _ {i - 1} - a _ {i - 1}$，则权值变成了 $c _ {j + 1} - d _ i$。

考虑如何计算没有连续段经过 $0$ 的结果。转化为选一个 $d$，再选一个 $c$，再选一个 $d$……这样的。然后可以直接 dp：$f _ {i, 0 / 1}$ 表示前 $i$ 个，现在该选 $d$ 或是选 $c$ 时的最大值。最后取 $f _ {n, 0}$ 即可。

考虑有连续段经过 $0$ 前面。和上面类似，不过是先选一个 $c$，再选一个 $d$。但这样还没有算好经过 $0$ 那一段的贡献。可以考虑将第一个 $c$ 向后挪 $n$ 次，只需要加上 $a _ {n - 1} - b _ {n - 1}$ 即可。

代码。

必要条件就是充要条件。

感觉这个题很乱阿。乱猜一个充要条件，乱写一个 dp，乱构造一下就行了。

充要条件大概是，正着看和反着看（反转串并将左括号变成右括号，右括号变成左括号）时，都满足对于任意前缀，左括号数量乘二大于等于右括号数量。

必要性比较显然，大概就发现如果小于就无论如何都造不出来。充分性可以构造证明。

不过我做题的时候就直接写个暴搜发现对了，然后先做的计数。

计数大概就，dp 状态乱设一个，比如我的是 $f _ {i, p, s}$ 表示前面填了 $i$ 个括号，前面的左括号数量乘二减右括号数量为 $p$，钦定后面的这东西是 $s$，然后 $n$ 的答案是 $\sum f _ {n, p, 0}$。转移大概是 $f _ {i, p, s} \to f _ {i + 1, p + 2, s + 1}$ 和 $f _ {i, p, s} \to f _ {i + 1, p - 1, s - 2}$ 这样的，注意保证 $p, s$ 非负。

构造就，也是正着做一遍反着做一遍。最初全设成绿色。从左到右扫，直接维护左括号减右括号，如果小于零了，就把最近的两个右括号染成一蓝一红。

为什么正着做时和反着做时不会互相影响？其实染的右括号都在染的左括号的左边，不然就不会染。

代码。

考虑判定一个序列是不是 ZalSequence。

感觉这个题更乱了阿。

判定大概就是，考虑当前数列中最小的数字 $t$，它组成的连续段长度一定是偶数，设其为 $c$，然后它一定由 $c \div 2$ 个 $t + 1$ 分裂而来。枚举 $t$ 直接做。

构造和判定类似的，枚举 $t$，如果某个连续段长度是奇数，那至少要补一个 $t$，位置任意。这样一定是填数最少的方案。之后如果 $k$ 还有剩余，那就随便分裂几个填进去的数即可。

代码。

对于一个 $S'$ 分析其答案。

感觉这个题好困难阿。这个题不会做，K 教我的。K 直接切掉这场所有困难题，太强大。不过 K 的做法比较神秘，没整明白，所以就没法说明。下面是从洛谷题解看的。

将 C 看作 $1$，T 看作 $-1$。删掉的必然是 T。考虑一个贪心：反复从前往后找到第一个和小于 $0$ 的位置，删掉那里的 T；之后从后往前一样做这个过程。正确性比较显然，不证了（）

考虑优化它。设 $p _ i$ 表示 $i$ 处的前缀和， $s _ i$ 表示 $i$ 处的后缀和。那么从前往后删的时候删的 T 就是 $p _ i$ 第一次是 $-1, -2, \cdots, \min\{p\}$，删的次数就是 $-\min\{p\}$。在 $i$ 处删 T 相当于给 $[1, i]$ 的 $s$ 加一。设 $s' _ i$ 为这时的后缀和，考虑从后往前的时候删的，就是 $-s' _ {\min}$。
考虑 $s' _ i$ 是什么：$s _ i + (\min _ {j < i} \{p _ j\} - \min\{p\})$。
考虑答案是什么：$-\min\{p\} - \min\{s'\}$，就是 $-\min _ {i} \{s _ i + \min _ {j < i} \{p _ j\}\}$，就是 $\max _ {j < i} \{- s _ i - p _ j\}$。把 $s _ i$ 换成总和减 $p _ {i - 1}$，就是 $- sum + \max _ {j \le i} \{p _ i - p _ j\}$。
前面是区间和，后面是区间最大子段和，易于维护。

代码。