NEUQ 2025 Winter Contest 1 Solution

stl 做法 1：

使用 map<int,vector>。对于每个值记录每次出现的位置，询问时直接输出即可。

stl 做法 2：

使用 map<pair<int,int>,int>。对于序列 $a$ 中每个数用另一个 map 求出它当前是第几次出现在序列 $a$ 中，与这个数的值组成一个 pair，用 map<pair<int,int>,int> 记录当前 pair 对应的下标，询问时直接输出即可。

以上两种做法时间复杂度均为 $\Theta((n+q)\log n)$。

非 stl 做法众多，不在题解中阐述。

枚举先将文件传输至哪一台打印机，分别计算可以打印的文件数，取较大值输出即可。

时间复杂度为 $\Theta(1)$。

定义一个区间结构体，包含两个元素 $l$ 和 $r$，代表一段区间，对于两个区间结构体 $x,y$，定义 $x<y$ 当且仅当 $x.r<y.l$。

用 set 储存以上区间结构体，称 set 的名字为 $s$，对于一个区间结构体 $x$，它与 set 中所有区间均不相交当且仅当 s.find(x)==s.end()。

对于一个 $i$，我们从第 $i$ 个区间开始，往 set 中插入区间，直到下一个区间与 set 中的区间相交为止，此时加到的区间下标即为 $a=i$ 时的答案。

从 $a=i$ 的情况变为 $a=i+1$ 的情况，只需要在 set 中删除第 $i$ 个区间，然后重复执行以上过程即可。

于是可以在 $\Theta(n\log n)$ 的时间复杂度内解决该题。目前没有更快的做法。

这是一个非常实用的 trick，建议大家学习。

显然，两个 BOT 会相撞当且仅当它们的 $c$ 不同且 $p-t$ 相等。

对于不同的 $c$，记录每种 $p-t$ 的出现次数。最后对于每种 $p-t$，取两种 $c$ 中出现次数的较小值相加即可。

实际实现时可以提前开一个大数组，取中间的地址，用指针访问负下标。也可以每次加一个固定值，将负下标转移为非负下标。也可以使用 map，直接访问负下标。

认为 $n,p,t$ 同级，则时间复杂度为 $\Theta(n)$ 或 $\Theta(n\log n)$。

注意到：对于一个 $r$，不同的 $\gcd(a_l,a_{l+1},\dots,a_r)$ 至多只有 $\lfloor\log a_r\rfloor+1$ 种。

当我们对于一个 $r=x$ 求出了所有不同的 $\gcd(a_l,a_{l+1},\dots,a_r)$ 并找到了与之对应的最小的 $l$ 后，要求出 $r=x+1$ 的情况。只需要在 $l$ 的集合中插入 $x+1$，并将对应的 $\gcd$ 相同的 $l$ 只保留最小的即可。

于是对于每个 $r$，我们都可以求出所有不同的 $\gcd(a_l,a_{l+1},\dots,a_r)$ 和与之对应的最小的 $l$，依次对这些区间中长度至少为 $k$ 的区间计算优美程度，并取最大值即可。

时间复杂度为 $\Theta(n\log^2 a)$，常数较小，可以通过本题。精细实现或使用科技可以做到 $\Theta(n\log a)$ 的复杂度。