本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-13 23:06:03

:::::warning[注释] 除特殊标记外，本文中变量均为整数。
::::: :::::info[闲话] 可能是暑假最后一篇了。
:::::

A. Gabriel and Caterpillar：

:::::info[题目基本信息] 考察：数学，模拟（$800$）。
题目简述：
小 K 发现了一只毛毛虫，它在第 $0$ 天 $14$ 点位于高度 $h_1m$，它在每天 $10\sim22$ 点向上以 $am/h$ 的速度爬，其余时间在向下以 $bm/h$ 的速度掉，问第几天的 $14$ 点他的高度会到达 $h_2m$（高度可以为负），不可能给出 $-1$？
数据范围：

• $1\le h_1,h_2,a,b\le 10^5$ ::::: 容易发现，若一天内还没有爬上去，且最后位置回到了 $h_1$ 甚至更低，则一定爬不上去。 否则由于数据范围较小，直接模拟即可。 时间复杂度为 $\Theta(V)$，空间复杂度为 $\Theta(1)$。

B. z-sort：

:::::info[题目基本信息] 考察：数学，构造（$1000$）。
题目简述：
小 X 收到了一个序列 $\{a_n\}$，现在将其排序，使得（$1\le i\le n$）：

• 若 $2\mid i$，则 $a_i\ge a_{i-1}$。
• 若 $2\nmid i$，则 $a_i\le a_{i-1}$。

构造一组合法解，若无解输出 Impossible。
数据范围：

• $1\le n\le 1000$
• $\forall i\in[1,n],1\le a_i\le 10^9$ ::::: 容易发现若 $\forall i,j\in[1,n],2\mid i,2\nmid j,a_i\ge a_j$，则这种序列是满足要求的，直接按照这样排序模拟即可。 时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

C. Foe Pairs：

:::::info[题目基本信息] 考察：STL，双指针（$1800$）。
题目简述：
小 I 收到了一个长度为 $n$ 的排列 $\{p_n\}$，现在给出 $m$ 组限制，第 $i$ 组限制为 $a_i,b_i$，问有多少组区间 $[l,r]$ 满足：

• $1\le l\le r\le n$
• $\forall i\in[1,m],j\in[l,r],a_i\ne p_j\lor\forall j\in[l,r],b_i\ne p_j$

数据范围：

• $1\le n,m\le 3\times 10^5$
• $\forall i\in[1,n],1\le p_i\le n$
• $\forall i\in[1,m],1\le a_i,b_i\le n$ ::::: 首先我们要找到 $a_i,b_i$ 的具体位置，所以我们要开桶（较小的设为 $idxa$，较大的设为 $idxb$），然后找到若 $l\le idxa\le r$，则 $r$ 最少到哪里。
  首先一个点的可以直接预处理，多个点的话先放一边。
  然后我们想到若左端点右移，则右端点的取值范围也会右移，所以我们想到双指针。
  我们回到多个点的右端点的取值范围其实就是取最小值，同时也要支持增加或减少，所以我们想到 multiset，最后直接模拟即可。
  时间复杂度为 $\Theta(n\log n+m)$，空间复杂度为 $\Theta(n)$。

D. Nested Segments：

:::::info[题目基本信息] 考察：树状数组，线段树（$1800$）。
题目简述：
小 A 收到了 $n$ 条线段，它们都在同一条数轴上，问每条线段各包含几条其他的线段（保证没有线段完全重合）。
::::info[包含的定义] 若对于所有的在线段 $a$ 上的点都在线段 $b$ 上，则称线段 $b$ 包含线段 $a$。
:::: ::::info[完全重合的定义] 若线段 $a$ 包含线段 $b$ 且线段 $b$ 包含线段 $a$，则称线段 $a$ 和线段 $b$ 完全重合。
:::: 数据范围：

• $1\le n\le 2\times 10^5$ ::::: 容易发现若线段 $a$ 的两端为 $l_a$ 和 $r_a$，线段 $b$ 的两端为 $l_b$ 和 $r_b$，线段 $a$ 包含线段 $b$，则 $l_a\le l_b\le r_b\le r_a$。
  容易发现这就是一个二维偏序问题，将线段端点离散化后按左端点降序排序，用树状数组或线段树统计答案即可。
  时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

E. Pursuit For Artifacts：

:::::info[题目基本信息] 考察：边双连通分量，dfs（$2300$）。
题目简述：
小 L 收到一张 $n$ 个点 $m$ 条边的简单无向连通图，边边权为 $0$ 或 $1$。
小 L 要在这张图中游走，每条边只能通过一次（两个方向加起来一次），问是否存在一条 $a$ 到 $b$ 的边，满足路径中至少有一条边边权为 $1$。
数据范围：

• $1\le n\le 3\times 10^5$
• $0\le m\le 3\times 10^5$
• $1\le a,b\le n$ ::::: :::::info[闲话] 发现自己的边双连通分量是假的。
  ::::: 容易发现若一个环（一个双联通分量）中存在一个边权为 $1$ 的边，那么经过这个双联通分量的路径一定有方法使路径满足条件。
  上面的性质启示我们用 tarjan 缩点，缩完点后直接 dfs 判断即可。 时间复杂度为 $\Theta(n+m)$，空间复杂度为 $\Theta(n+m)$。

F. Ants on a Circle：

:::::info[题目基本信息] 考察：数学（$2800$）。
题目简述：
小 Z 发现了一个环，长度为 $m$，位置编号为 $1$ 到 $m$，在这个环上有 $n$ 只蚂蚁，它们分别位于不同位置且面向不同方向。
小 Z 在那里看了 $t$ 秒，每只蚂蚁都会以 $1m/s$ 的速度向自己面向的方向前进，中途遇到其他蚂蚁会调头，由于他忙人多忘事，他忘了最后他们的位置，但是他记得初始状态，他想让你给出终止状态。
数据范围：

• $2\le n\le3\times 10^5$
• $2\le m\le 10^9$
• $0\le t\le 10^{18}$ ::::: 我们按照常规套路，先假设这些蚂蚁碰头后会互相穿过去，这样我们就可以求出所有蚂蚁的位置，但无法知道谁是谁的。
  这时候我们注意到由于掉头，所以每只蚂蚁的相对位置一定不会改变，也就是说我们得到一个性质：一只蚂蚁一定一直在另外两只蚂蚁中间。
  那么我们把每秒从位置编号较小的蚂蚁开始编号，那么编号改变只可能有以下情况：

1. 两只蚂蚁相遇： 这种情况其实根据上面那条性质就可以搞定了，问题在于下面这一种。

2. 一只蚂蚁从 $m$ 到 $1$ 或者从 $1$ 到 $m$：
   这种情况由于情况 $1$ 已经解决就比较简单了，每只蚂蚁经过 $m$ 到 $1$ 或 $1$ 到 $m$ 的次数能 $\Theta(1)$ 求出，那么对于不同蚂蚁而言（这里以从 $m$ 到 $1$ 为例，$1$ 到 $m$ 同理）：

   • 对于自己，自己的相对位置编号会减去 $n-1$。
   • 对于其它蚂蚁，它们的相对位置编号会加上 $1$。

   那么注意到这两种操作在模 $n$ 意义下是等价的，所以统一处理即可。

所以，将原位置和终止位置排序，记录答案，统一输出即可。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(m)$。