比赛记录（2.14~省选）

· · 个人记录

MX-X 二重身赛

T3 调太久了没过掉 T4。

T4 的关键结论是对于一个 x，最大的答案取到的位置 y 一定是 x 的邻边。

Goodbye Yisi

A

考虑只让这个数每次减去 2^i 来达成目标。

分为两个阶段：第一个阶段是每次减去 lowbit 以让 y 的 2 因子最多。

第二个阶段是每次减去最大的 2^i 可以达成目标。

第二个阶段可以拆分 y-x 的二进制表示，我做繁了。

难度：【0】

B

关键结论：定义物品的性价比为 \dfrac{v_i}{w_i}。若总重量为所有性价比 \ge 1 的物品的重量之和，则绝对不会选到性价比 <1 的物品。

证明：如果替换若干个性价比 \ge 1 来换取若干个性价比 <1 的物品则一定劣。

分治。设计当前有若干个组，每组包含了确定当前 v_i\in [l,r] 的物品。

选一个 mid 切成 [l,mid],[mid+1,r] 两组。然后判断每个物品在哪组里。直接将这组的 w_i 都设成 mid+1 即可。

难度：【1】。

C

时光倒流。首先最小值取到的方式手玩一下就是每次和最小值合并。

然后判断如何和最小值合并。定义序列中所有的最小值为红点，其他的点为黑点。每次要求为选择两个连通块合并，这两个连通块至少要有一个是红的。

接下来我的做法会比较抽象。但是标准做法应该没那么麻烦。

容斥，钦定这次的连通块都是黑的。这次钦定在原树上画出了一个连通块，保证是黑的。那么考虑这个连通块之前是怎么形成的。不难发现之前的每一步都可以选择钦定或者不钦定，这样总方案数是 0。所以这样的钦定操作只能在合并涉及的两个连通块都退化成单点的情况下钦定。

我们设钦定边为蓝边，其他边为黑边，从原树上看。满足以下两个限制：

这是拓扑序计数。不难发现这些限制构成树。所以是和 SAO 那题一样的树的拓扑序计数。

从下到上 dp，记录 u 父亲的边是否是蓝色，u 父亲的边对应是拓扑序计数上所在的子树大小为 j。

如果子节点有蓝边，则其他子节点的黑边都要连向这个蓝边，然后有一条逆顺序的边也就是连向 u 的边，容斥处理掉。

如果子节点没有蓝边很简单。如果 u 到 u 父亲的边是蓝色则向子节点连边。转移很简单。

难度：感觉可以【2-】。

ARC215

A

考虑贪心，我们发现操作只有两种：

枚举第二种操作做几次，每次找到最远的两个僵尸合并即可。

难度：【0】。

B

题意相当于一种颜色的两个珠子被划分入的组不同。

想要让组数少一些，相当于让相邻两个珠子在同一个组内数量尽量多。

我们给这两种限制建图，现在第一种限制要全部满足。

如果我们选出若干个第二种限制，并且所有限制连成了一棵树，那么一定有解。

现在我们要找出若干个第二种限制连成一棵树，这是类似 MST 的方法，直接做。

显然会选出恰好 n-1 个第二种限制。

然后再跑一遍 dfs 找出选的珠子就好了。

难度：【0】。

C

考虑什么人无法成为最后留下的人。

把所有人按照 a 排序，然后考虑一个前缀的人是否被剩下的人全部偏序即可。如果是的那么这个前缀无法成为最后留下的人。

证明不会，感性理解。

难度：【0】。

D

考虑计数 a 而非 s。

可能会算重，考虑代表元思想。 首先如果 $a_1$ 确定了那么剩下的也确定了。 操作：假设 $a_1$ 增加 $1$ 那么 $a_3,a_5,a_7$ 这些都会增加 $1$，$a_2,a_4,a_6$ 这些都会减小 $1$。 显然通过这种方式可以得到所有这个 $s$ 可以表达出的 $a$。 我们定义一个 $s$ 的代表元满足无法再次进行合法的操作。 那么这要求奇数项有 $m$ 或者偶数项有 $0$。 容斥，数奇数项 $<m$ 偶数项 $>0$ 的序列。 好数。 难度：【0】。 ## E 直接将操作建图。如下几步： + 把所有能变成 $1$ 的点变成 $1$。 + 枚举最终是 $1$ 的点，通过扩散将这个点能到达的点反着变成可能的 $0$。 难度：【0】。但是我没调完。 # 省选模拟赛 #1 ## 赛后总结 省流：没给 T2 调出拼的 $64$ 的分，失败的人生。 ## T1 [原题链接](https://www.luogu.com.cn/problem/P14646)。 结论一：若有一个柱只含有一个 $1\sim x$ 的前缀的盘子，则操作次数为 $n-x$。特别的，若有空柱次数为 $n$。 结论二：记某个柱子上最大盘的最小值为 $a$，若一个柱子的最小盘比 $a$ 大，则选出这样柱子大小的最小值 $z$ 并且移动到那个盘上，造出一个空柱，操作次数为 $n+z$。 难度：【0】。 ## T2 [原题链接](https://www.luogu.com.cn/problem/P13508)。 这题难完了吧。 先刻画贪心策略，这一步很简单。 我们把 $u+1\sim n$ 的点中值域在 $a_u\sim a_v$ 之间的点拿出来，我们要选择一个能跳到的点跳。 那么贪心的肯定是跳到 $a$ 最大的点。 --- 问题转化成，$u$ 可以跳到 $[u+1,r_u]$ 中的，值域在 $a_u\sim a_v$ 的点。 考虑**转换维度**。初始时我们在 $t=a_u$。 接下来令 $t<y\le a_v$，且 $b_t<b_y\le r_{b_t}$。然后操作 $t$ 到 $y$。 --- 考虑分治，若 $a_u\le mid$ 且 $mid<a_v$，则处理这些询问。 我们让每一个点 $u$ 跳到第一个值 $>mid$ 的点 $to_u$ 并把询问改成 $(to_u,v)$。 我们在值域上跳跃。首先对每个点 $u$ 求出其： + 若跳跃后仍在 $[l,mid]$，则跳到 $fa_u$。 + 若 $v\ge c_u$，则 $u$ 会跳到 $[mid+1,r]$。 用 $fa_u$ 建立一棵树，现在： + 我们从点 $u$ 出发，经历若干个祖先后，从祖先 $T$ 离去，因为 $c_T\le v$，再从 $T$ 暴力跳一步即可得到 $to_u$。 --- 上面这个问题可以倍增找到 $T$，接下来从 $T$ 往后跳可以线段树区间查询最大值。 递归次数只有 $O(\log n)$ 次，所以复杂度是 $O(n\log^2 n)$。 --- 下面在我的学习笔记里再尝试加入一个叫做算法流程的东西。 算法流程就是，要详细到对着写就能过。。。不需要脑子。 算法流程： + 按 $a$ 从大到小加入并查集，用并查集维护连通块，若连通块大小超过 $d$，则在 set 中加入，查询 set 中 $p$ 的后继，可以求出 $r_p$。 + 把询问离线，挂在一棵猫树上。 + 遍历猫树中的节点，进行分治操作。 + 用线段树从 $mid$ 扫到 $l$ 加入 $(b_y,y)$，然后查询 $b_t+1\le b_y\le r_{b_t}$ 中 $y$ 的最大值。记这个值为 $fa_i$。 + 把 $[mid+1,r]$ 都类似的加入线段树并查出 $c_u$。 + 求出后立马开始倍增，定义 $f_{i,j}$ 表示 $i$ 在树上向上跳 $j$ 步，路径上所有点（不包括终点）的 $c$ 的最小值。 + 然后转而考虑所有询问。对于每个询问从 $u$ 开始倍增，如果 $f_{u,j}>v$ 就跳。如果跳到树外面就是无解，拎出来。 + 否则可以求出最后跳到的节点 $T_{u,v}$。然后按照 $v$ 扫描线，扫到时加入了所有 $[mid+1,r]$ 中的二元组，查询最大值，可以得到 $u'$。 + 然后清空线段树并且把 $(u',v)$ 塞到猫树右边节点中。 --- 难度：【2】。 ## T3 [原题链接](https://www.luogu.com.cn/problem/P11567)。 题意描述： 你有一个图，请你删去图中的若干条边，使得留下的图联通。 对于剩下的图，有 $k$ 个限制，第 $i$ 个限制要求限制中 $p_i$ 到 $q_i$ 的所有路径上都只有红边（表示驻守军队）。 问你方案数。$1\le n\le 16$。 ## 变换 首先要解决这个问题：求一个图的边双连通子图个数。 给任意一个图做边双缩点，会得到一棵树。 我们给 $\{1,2,...,n\}$ 划分成若干个不交的子集 $S_1,S_2,...,S_k$。每个子集代表一个连通图。这些子集之间用 $k-1$ 条边连接并形成一个大连通图，容斥系数为 $c^{k-1}$。其中 $c=-1$。这是自然的。 我们称这 $k-1$ 条边是割边。现在我们求出所有点集 $S\subseteq \{1,2,...,n\}$，且只加入两端编号都 $\le i$ 的割边，$S$ 上的子图形成一个连通图的方案数。记这对应了一个集合幂级数：$f_i$。注意这并不是只考虑了 $\le i$ 的点。 $i\notin S$ 的情况是平凡的，假设 $i\in S$。我们考虑删去所有一端是 $i$ 的割边后，点集 $S$ 的情况。这把 $S$ 分成了若干个连通块： + $T_1,T_2,T_3,...,T_l$。这些连通块**不包含**点 $i$。 + $P$。这个连通块**包含**点 $i$。 接下来设计集合幂级数操作。 设计辅助集合幂级数 $g_i$。我们定义：$g_{i,S}=[i\notin S] f_{i-1,S}\cdot coef(S,i) \cdot c$。 其中 $coef(S,i)$ 表示点集 $S$ 中，$< i$ 的点与 $i$ 的连边数。这个定义给出了 $S$ 这个连通块与 $i$ 连出割边的方案数。 我们有：$f_{i,S}=(f_{i-1} \cdot \exp(g_i))_S$。 若 $i\notin S$，则 $f_{i,S}=f_{i-1,S}$。边界条件为 $f_0=F$。 这里是理由：$P$ 代表 $f_{i-1}$，$\exp$ 也就是自由划分。 定义上面一个问题为 $G=\mathrm{ans}(F,c)$。 ## 解法 限制对应的操作：将所有 $p_i$ 所在边双到 $q_i$ 边双所在边双经过的所有边标记为**红色**。 我们找出所有**红边涉及到的点**，记为红点，显然对于每个 $(p_i,q_i)$，$p_i$ 和 $q_i$ 都会被找出来。 这些红点，在**缩点后的树**上可以构成若干个红色连通块。 我们尝试计算一个点集 $S\subseteq \{1,2,...,n\}$ 的导出子图，通过删边，**构成了一个红色连通块**的方案数。 计算方式考虑使用上面的问题。我们构造一个辅助的集合幂级数 $F$，表示删边后 $S$ 的导出子图是一个连通图，并且对于一对限制 $(p_i,q_i)$，这两个点要么都在 $S$ 中，要么都不在 $S$ 中。 Hint：考虑 $F'=\mathrm{ans}(F,-1)$ 的意义。 选出一组划分，相当于删去缩点后树上的若干条边，这样剩下了若干个连通块，这些连通块内，“对于一对限制 $(p_i,q_i)$，这两个点要么都在 $S$ 中，要么都不在 $S$ 中。” 由于这样，红边实际上不会经过删掉的这条边。所以删掉的边一定是不合法的，那么因为删掉的边的权值为 $1+(-1)$，所以我们用这种方式容斥掉了。 所以 $F'$ 就是上面说的，一个点集 $S\subseteq \{1,2,...,n\}$ 的导出子图，通过删边，**构成了一个红色连通块**的方案数。 --- 接下来统计黑色点和黑色边的情况。 先算黑色连通图的集合幂级数。**此时每个点还可以选择驻守军队**。 我们设 $G_0=3^{coef(S)}$，对其作 $\ln$ 就可以求出 $G$ 也就是连通图的方案。 然后算 $G'=\mathrm{ans}(G,-2)$，这也是自然推广。$G'$ 就是黑色边双的方案。 --- 接下来统计红点连通块（注意这里的红点是缩点后树上的意义）与黑色边双的组合。 因为把这些东西组合起来的是可以驻守军队的边。所以最终的集合幂级数就是 $\mathrm{ans}(F'+G',-2)$。 --- 难度：【3】。 # 省选模拟赛 #2 ## 赛后总结 发现前两个题其他人都做过但我没做过，比较破防。然后搓了两个小时搓出来了 T2，然后胡了一个 T1 做法，出分发现只有 $8+91+0$。 下午花了两个小时研究自己 T1 为什么错了，然后发现完全是假的，很破防。 晚上不知道在干嘛。 ## T1 [原题链接](https://www.luogu.com.cn/problem/P8428)。 下午花了两个小时才知道自己假了，火大。 直接说正解。先处理出每个点到最近的羊的距离 $dis_u$。 我们每次找到没有被覆盖的，深度最大的羊，然后找到这个羊的一个深度最浅的祖先，使得这个祖先可以覆盖到这只羊。然后在这个点上放牧羊人，从这个位置搜索，只走 $dis_v+1=dis_u$ 的边，走到的羊都可以被这个牧羊人控制。 难度：【1+】。 ## T2 [原题链接](https://www.luogu.com.cn/problem/P12558)。 将所有人和怪物排列在数轴上。 可以先设计出一些 dp，但是这些 dp 都无法做到 $O(n^2)$。 我们的诉求是**不使用传统的从左到右 dp**。 考虑如下策略：每个向右匹配的人，从右到左往最右侧的怪物匹配。每个向左匹配的人，从左到右往最左侧的怪物匹配。 所以怪物分成两种，往右匹配和往左匹配，并且这被一条线分割开。 这个形态使得我们可以分步 dp。 设第一个 dp 是从左到右，$f_{i,j}$ 表示前 $i$ 个人中有 $j$ 个向左。转移时如果遇到向右就不管。 设第二个 dp 是从右到左，$g_{i,j}$ 表示后 $i$ 个人中有 $j$ 个向右。转移时如果遇到向左就不管。 然后合并一下就好了。 难度：【2-】。 ## T3 [原题链接](https://www.luogu.com.cn/problem/P13542)。 这个题应该是足够难的。 先求出 dfs 树。接下来分类讨论几种情况： + 割断了两条非树边。显然没有用。 + 割断了一条树边和一条非树边。 + 割断了两条树边。 对于第二种情况，显然必须是这条树边上方的唯一一条非树边，只需要求出树上跨过这条边的路径 $(a_i,b_i)$ 的数量就好了。 定义边 $S_i$ 为第 $i$ 条树边上方的所有非树边构成的集合。定义 $c_i$ 为跨过边 $i$ 的路径 $(a,b)$ 的数量。 对于第三种情况，记割掉的两条边为 $i,j$ 那么又有几种情况： + $S_i=S_j=\varnothing$。答案为 $c_i+c_j$。 + $S_i=\varnothing,S_j\neq \varnothing$。答案为 $c_i$。 + 其他情况。 考虑其他情况。首先为了让图不连通，$S_i=S_j$ 是必然的。那么我们可以用异或哈希来判断这一点。 因为这两条边在同一个等价类里，所以 $i$ 和 $j$ 一定有祖先后代关系。割断之后，$i$ 到 $j$ 中间的连通块与其他点分离。 通过容斥我们可以得到答案为 $c_i+c_j-2g(i,j)$。其中 $g(i,j)$ 是同时跨过 $i,j$ 两条边的路径数。 虽然但是，这个东西不知道为啥就有决策单调性。具体的，随着 $i$ 往子树里走，$j$ 也是更低的。 因为这个东西显然又没有严格单调性，所以决策单调性分治。 因为把同一个等价类拿出来和祖先后代链就是一个意思的了，所以决策单调性分治是一样写的。 然后考虑怎么快速查询 $g(i,j)$。显然同时跨过两条边拍成 dfs 序后是矩形查询，在线的话主席树就好了。 时间复杂度 $O(n\log^2 n)$。 难度：【3】。 # MX-X 欧尼恩赛 ## T5 有以 $1\sim 10^{100}$ 编号的 $10^{100}$ 种货币。 对于 $1\le i<10^{100}$，若你有 $b$ 个第 $i$ 种货币，则可以兑换成 $a$ 个第 $i+1$ 种货币。这种兑换可以进行很多次，且每次兑换的条件只需要你有至少 $b$ 个第 $i$ 种货币。 初始时你只有 $n$ 个第 $1$ 种货币。现在你想通过若干次兑换使得货币总数最少，请求出这个最小值。 $1\le T\le10$，$1\le n\le 10^{18}$，$1\le a<b\le 10^{18}$。 ## 算法一 直接从低往高模拟兑换过程。 首先第一种会留下 $n\bmod b$ 个货币。然后第二种会有 $\lfloor \dfrac{n}{b}\rfloor a$ 个货币。 假设第三种时有 $xa$ 个货币。则 $x=\lfloor \dfrac{\lfloor\dfrac{n}{b}\rfloor a}{b}\rfloor$。 不妨记 $y=\lfloor \dfrac{n}{b}\rfloor$。现在我们想要知道 $x$ 和 $y$ 的关系。也就是 $x=\lfloor \dfrac{ya}{b} \rfloor$。 如果暴力做这个过程，我们分析这个过程的复杂度。 一方面，$x<y$，所以复杂度显然不超过 $O(\dfrac{n}{b})$。 另一方面，复杂度也不超过 $O(\log_{\frac{b}{a}} n)$。 考虑分析第二种的复杂度，不难发现这是 $O(\log_{\frac{b}{a}} e \ln n)$。 分析 $\log$ 函数考虑其近似。有一个算 $e$ 的方法是 $\left(1+\dfrac{1}{x}\right)^x$，在正整数 $x$ 很大的时候就逼近 $e$，所以我们宣称这个东西的复杂度是 $O(\dfrac{a\ln n}{b-a})$ 的。实际上缩放一下就能证明，在此略去。 如果 $a$ 和 $b$ 不是一个量级的，那么假设两者相比为 $2$，则复杂度就是一只 $\log$ 了。所以这是平凡情况。于是 $a$ 与 $b$ 量级相同。 由于上式在 $b-a=1$ 时最劣，所以暴力模拟的复杂度为 $O(\sqrt{n\log n})$。不需要根号分治。 ## 算法二 这样显然无法通过，考虑优化。 根据 $b-a$ 的最劣情况我们可以想到一个很妙的优化：$x=\lfloor \dfrac{ya}{b}\rfloor=\lfloor y-\dfrac{y(b-a)}{b}\rfloor=y-\lceil \dfrac{y(b-a)}{b}\rceil$。 我们让 $\lceil\dfrac{y(b-a)}{b}\rceil$ 相同的为一段，具体的说，若 $y>0$，则设当前的 $\lceil\dfrac{y(b-a)}{b}\rceil=z$，则我们考虑 $O(1)$ 的让 $z$ 减少至少 $1$。 显然这一段是等差数列，可以快速跳。 具体的，我们求出当前的 $z$，然后现在有一个不等式也就是 $\dfrac{y_{\min}(b-a)}{b}>z-1$。这个 $y_{\min}$ 就是这个等差数列的临界值。 可以得到 $y_{\min}=\lfloor\dfrac{(z-1)b}{b-a}\rfloor +1$。然后我们求出在临界值之前的等差数列 $y\sim y'$，也就是 $y'=y-kz$。 又因为 $y-kz\ge y_{\min}$，所以 $k=\lfloor \dfrac{y-y_{\min}}{z} \rfloor$。 所以等差数列 $h$ 就是 $h_0=y,h_1=y-z,...,h_k=y-kz$。当然还有最后出去的项 $h_{k+1}=y-(k+1)z$。新的 $y$ 就是 $h_{k+1}$。 然后考虑怎么算这 $0\sim k$ 轮剩下的硬币数量。可以得到 $\displaystyle \sum_{i=0}^{k} h_{i+1}b-h_ia$。这就是等差数列求和而已。 可以得到 $\dfrac{(y-z+y-(k+1)z)(k+1)b}{2}-\dfrac{(y+y-kz)(k+1)a}{2}$。 略微化简得到 $\dfrac{((2y-(k+2)z)b-(2y-kz)a)(k+1)}{2}$。 然后好像算完了。 ## 复杂度 然后考虑分析优化后的时间复杂度，首先复杂度不超过 $\dfrac{n(b-a)}{b^2}$。另外也不超过 $\dfrac{b}{b-a}$。 我们还设 $m=\dfrac{b}{b-a}$，则复杂度改写为 $\min(\dfrac{n}{m^2(b-a)},m \log n)$，显然最劣情况还是 $b-a=1$。 取根号分治的复杂度分析，复杂度当 $m=n^{\frac{1}{3}}\log^{-\frac{1}{3}} n$ 时达到 $O(n^{\frac{1}{3}}\log^{\frac{2}{3}} n) $。 由于实际上并不需要根号分治，所以其实跑不满。 经过手动测试，可以宣称 std 拆成的等差数列数不超过 $2\times 10^6$。 难度：【1】。 # 省选模拟赛 #3 ## 赛后总结 T1 枚举了 $a+b$，然后就死了。谁问我了。 upd：其实也可以，但是我写死了。 T3 没怎么想，可能再想想就会了。 ## T1 [原题链接](https://qoj.ac/problem/7239)。 不是为啥换个方向推就很好做。 设 $a<b<c$。有限制 $a<c-b$。 可以发现若 $b,c$ 固定则 $a$ 在此限制下越大越好。 枚举 $k=c-b$，在 $a,k$ 固定的限制下 $b$ 越小越好。 所以记边长构成的集合为 $S$，则找最小的 $b$ 满足 $b+k\in S,b\in S,a<b$。这只需要用 bitset 的 _Find_next 函数就好了，常数非常小。 总结：什么时候能想到好做做法。 --- 好吧其实原来的做法也是能做的。 枚举 $a+b$ 后，找最小和最大的 $c$ 就好了。 难度：【1+】。 ## T2 难度：我不会流子，【3】。 ## T3 [原题链接](http://qoj.ac/problem/15325)。 没有看懂这个操作到底是个啥导致的。 先观察一个区间 $[l,r]$ 在经过父区间的操作后会变成的形态： + $[l,r]$ 不变。 + $[l,r]$ 中，其他数不变，最大值变为这个区间内的最小值（具体是什么不重要，不妨记做 $1$）。 + $[l,r]$ 中，其他数不变，最小值变为这个区间内的最大值。 这极其简洁，所以如果我们不会算重的话，直接区间 dp 就可以了。 接下来尝试扔掉重复的情况。 先考虑朴素分割不交换的情况。 如果初始状态是 $a$，最终状态是 $b$。那么如果可以分割 $[l,s],[s+1,r]$，当且仅当 $a[l,s],b[l,s]$ 两个序列组成的元素是相同的。 如果这个 $s$ 是所有分割点中最小的，则 $[l,s]$ 是极大区间。 现在我们尝试设计更多限制。 + 首先如果存在一种朴素分割方案，则应当立刻分割。 + 假设分割出了 $[l,s],[s+1,r]$，则 $[l,s]$ 是极大区间，内部一定不能继续朴素分割。 考虑 $[l,r]$ 如果已经是一个极大区间，那么如何归位。 首先一定要使用交换操作。记交换的两个数是 $a,b$。 接下来**一定**会出现一个分割点 $s$。选择这个位置 $(s,s+1)$。接下来 $[l,s]$ 仍然是极大区间，$[s+1,r]$ 这个区间内部在 $b$ 之后的位置不可以分割。 --- 接下来我们说明分割情况只有四种： + 最小值右侧不可以分割。 + 最大值右侧不可以分割。 + 全都不可以分割。 + 全部都可以分割。 然后记忆化搜索就好了。时间复杂度 $O(n^3)$。 难度：【1+】或者【2】。 # 省选模拟赛 #3 ## 赛后总结 T1 签子，T2 推了一下结合打表过了 $k$ 为偶数，T3 写了个暴力。 $100+58+32=190$，我觉得打的还可以啊！虽然好像 T2 并不难。 可能更专注的话，打的会更好？ ## T1 直接拆位即可。 难度：【0】。 ## T2 首先这可以看成一条 $(1,1)$ 到 $(n,m)$ 的路径。 每个整点 $(i,j)$ 代表一条左部点 $i$ 到右部点 $j$ 的边。 偶数其实和奇数是一样的，本质上就是把路径的每一节拎出来记做一个序列 $a$，然后求 $\displaystyle \sum_{i-j=k-2} a_ia_j$。 ## T3 牛的。 如果要找字典序最大的子序列，只需要拿出所有后缀最大值就好了。 为了让找出的子序列出现两次，需要找到 $x,y$ 满足 $a_x=a_y$，然后在 $[l,x-1]$ 和 $[y+1,r]$ 两个区间分别找子序列。 记这样的 $(x,y)$ 对中最大的 $x$ 为 $s$。 考虑判定最后子序列的每一位是什么。 + $s$ 以后的单个数无法被选入，这意味着我们选的第一个数是 $[l,s-1]$ 中的最大值（取最靠前的那个下标）。 + 如果这个最大值接下来没有第二次出现，那么显然可以把 $l$ 移动到那个下标。 + 如果这个最大值的第二次出现在 $[l,s-1]$ 之间，那么一定也要被选入，移到那里。 如果这个最大值的第二次出现在 $s$ 之后，那么有两种选择： + 跳到第二次出现时，获得之后的后缀最大值。 + 老实地不跳出 $[l,s-1]$。 --- 我们要从 $[l,s-1]$ 的非严格前缀最大值里找到第一个可以跳出去的位置，并决定是否跳出 $[l,s-1]$。 此时第一步需要比较 $[p+1,s-1]$ 与 $[q+1,r]$ 的最大值。如果哪边胜出就不需要再比了。 但是我们发现如果两边相等，这其实对应了另一对 $x<s<y$。这时继续比较不再有意义，因为这对应了另一个决策点。从 dp 的角度来看就是重复子结构。 所以我们只需要找出第一次胜出的位置。 --- 于是我们只剩下了 $O(1)$ 次比较，至此可以 $O(r-l+1)$ 的复杂度内计算答案。 更进一步！ 更好的模拟上述过程。在离线的情况下，快速找到 $s$ 只需要找到 $i\ge l,las_i\le r$ 的最大 $i$，按照 $l$ 从大往小扫描线，写个树状数组或者什么即可。 对于每个 $s$，其可以维护当前 $[1,s-1]$ 的后缀最大值。这是一个单调栈，可以做弹栈。 单调栈上每个位置要记录其对应的 $las_i$，而我们还有一个属性是 $r$，这需要查询 $[las_i+1,r]$ 的最大值。当然 $las_i$ 也要 $\le r$ 才有意义。 。 # 省选 【1】【1】【3】【1】【3】【3】。 会赢吗。 >ささやかな願い事 > >“微不足道的愿望” > >無垢な希望や将来の夢 > >“纯净的希望和将来的梦想” > >祈りさえすればいつか叶うと > >“只要诚心祈祷有朝一日终能实现” > >誰に教わったんだっけ > >这句话又是谁教我的呢