A：

考虑如果现在在点 $i$，能否走到编号更小的点。如果可以，那么必然存在一个 $j \geq i>a_{j}$ 使得你可以走到点 $a_{j}$。

那么我们对于每个 $i$，将区间 $\left(a_{i}, i\right]$ 加一，从 $x$ 开始能走到的编号最小的点也就是 $x$ 左侧最近的 0 的位置。

带修问题可以直接用线段树维护，查询的时候使用线段树二分。

时间复杂度 $\mathcal O((n+q) \log n)$ 。

B：

由于一个棋子的两条路径无交且包含所有的边，所以对于每条边，每个棋子恰有其中一条路径包含它。

那么我们枚举其中一条边，要求所有棋子均经过它，那么所有棋子的路径选择方案就确定下来了。

多条边能同时在答案中当且仅当它们确定的方案一致，即每条边对应一个选择方案，需要选出最大的等价类。判断等价关系直接使用随机异或哈希即可，时间复杂度 $\mathcal O(m \log m)$。

C：

设外层、内层子序列分别为 $S=\left\{p_{1}, p_{2}, \ldots, p_{l_{1}}\right\}, T=\left\{q_{1}, q_{2}, \ldots, q_{l_{2}}\right\}$。

原先一层的情况下，我们可以要求 $\forall j \in\left(p_{i-1}, p_{i}\right), a_{j} \neq a_{p_{i}}$ ，即钦定一种子序列在最左的出现位置处统计到。

那么两层的情况下，我们考虑对内层进行 DP，设 $f_{i}$ 表示考虑到 $i$ 且钦定 $i$ 在 $T$ 内的答案，那么枚举 $T$ 中上一个位置 $j$ ，考虑 $(j, i)$ 中的数填入 $S$ 的方案数，有如下限制：

• 对于 $j<p<i, a_{p}=a_{i}$，要求 $p$ 不能在 $S$ 中。
• 令 $l$ 为最大的 $j<p<i$ 使得 $a_{p}=a_{i}$，必须存在 $l<q<i$ 使得 $q$ 在 $S$ 中。
• 对 $S$ 中每相邻两个数 $p, q$，要求 $\forall k \in(p, q), a_{k} \neq a_{q}$ 。

其中第一条限制是为了限制 $T$ 为 $S$ 中最左的，后两条限制是为了限制 $S$ 为最左的。

时间复杂度 $\mathcal O\left(n^{2}\right)$，空间复杂度 $\mathcal O(n)$ 。

D：

摆了。

对于一个数 $v$，取出最长的相邻两项和 $\leq v$ 的子序列，如果其长度 $\geq k$ 那么答案就 $\leq v$ 。

我们把 $2 a_{i} \leq v$ 的数称为「小数」，反之称之为「大数」。小数必定可连选，大数必定不可连选。

最优情况必定为小数全选，对于每相邻两个小数，如果它们之间最小的大数可选就选上。

那么我们按值域从小到大做扫描线，每次会将一些大数切换为小数。注意到相邻的小数之间显然均为大数，所以求出若干四元组 $(i, j, l, r)$ 表示在 $v \in[l, r]$ 时 $i, j$为相邻小数且对答案有 1 的贡献。

差分为对 $v \geq l$ 的单点加矩形求和，还需注意 $[i, j]$ 跨过端点时的贡献。

对这些四元组以及询问进行整体二分即可。

时间复杂度 $\mathcal O\left((n+q) \log ^{2} n\right)$，可以通过。

然而还可以继续优化！对于一个时刻 $v$，仍有贡献的四元组 $(i, j, l, r), l \leq v \leq r$ 的区间 $[i, j]$ 除端点外互不相交，那么数点可以降一维：只要求 $i$ 在区间内，此时只会算多包含右端点的一个贡献区间。

前驱后继可以类似地在整体二分中双指针维护，时间复杂度 $\mathcal O((n+q) \log n)$ 。