【题解】牛客练习赛72

A

考虑造一张图，让每个位置 向 的所有倍数连有向边，那么 向 连了一条边的话就表示第 个杯子里的数要比第 个杯子里的数小。

然后事实上，我们只需要考虑图中最长的链就可以了，假如这条链存在合法的放数字方案，那么其他的点一定也存在合法的放数字方案，而最长的链显然是 。

所以只需要判断 是否比 大即可。

B

一个区间的愉悦值其实就是颜色段数。

考虑尺取法，因为颜色段数是有显然的单调性的，当 固定时， 增大，颜色段数一定不会减小。

预处理出 数组， 表示左端点为 时，右端点至少取到哪里，可以使区间内颜色段数不少于 ，每次询问 时，只需要判断 是否不小于 即可。

不过也可以用前缀和来做，实现也很简单。

C

假如将每个位置 看作平面直角坐标系上的一个点 ，那么可以发现，在操作完后，所有点会被削成一个下凸包的形状。原因比较显然，对于所有还没贴到下凸包上的点，总存在一个点是可以操作的。

那么求出所有点的下凸包，对于凸包上两个相邻的点，他们之间的点的纵坐标形成了一个等差数列，随便求一求就可以了。

最后要输出到小数点后 位是唬你的，假装要卡精度的样子qwq，事实上你发现整个求和过程中的除法只有求等差数列时的除以 ，也就是说答案的小数点后只可能是 或 ，判一下就好了。

然而事实上似乎没卡掉，应该输出到30位qwq

D

比较套路的推式子：先考虑拆开 ，根据定义，如果 不互质那么 一定为 ，假如互质那么又因为是积性函数，所以可以拆成 ，于是有：

令 ，代入得：

令 ，代入得：

于是利用 就可以做除法分块了。

注意到 的两个参数满足 ，所以只有 个 是有效的，预处理时间复杂度就是 ，总时间复杂度 。

E

标程做法

先考虑在序列上的问题，要怎么处理单次询问：令 表示以扑克 的 正面/反面 数字作为顺子的结尾，最长的顺子长度，转移比较显然，如果 ，那么 ， 初值为 。其中 表示第 张扑克 正面/反面 上的数字。

由于保证了正反两面的数字不同，所以转移可以改一下：假如存在 ，那么 ，否则 。

在考虑进阶版本，如果每次询问序列上的一个区间要怎么做？

一个比较显然的技巧，假如 或 ，那么交换 ，然后就不需要讨论扑克翻面的情况了，问题变成了在两个序列上分别求区间最长顺子，下面就说其中一个序列的做法：令 表示以 结尾的最长顺子长度，先去掉头尾的顺子，然后中间部分求一下 就可以了，可以用 表之类的东西。

再回到树上问题，树上不是很好处理，考虑轻重链剖分，那么每条重链就是一个序列问题。询问的时候，找到 到 路径上要经过的所有重链，令 表示经过的上一个序列的最后一张牌上的两个数字， 表示以这个数字结尾的最长顺子，从一条重链转移到另一条重链时，只需要用到这些信息，即看一下上一条重链的末尾与当前重链的起点是否能合并，如果能，再看以 这条重链的起点 为起点的顺子最长能不能延伸到重链的末尾，如果能，那么让 直接加上重链长度即可，否则直接变成 重链末尾。

然后还要算一下每条重链内的答案，那么这就是序列上每次询问一个区间内的最长顺子，用上面的做法搞就好了。

然后代码就巨长……

验题人做法

验题人日常吊打出题人。

他使用了一个实现起来更方便的做法，大部分思路是类似的，但是用了一个方便的转化：考虑序列上的一个顺子，令每个位置上的数与位置编号做差，那么做差后一段连续的相同的数就对应原来一个顺子。

放到树上，就是令 ~ 这一段的数加上深度， ~ 这一段减去深度，然后可以用倍增来更方便地维护。

F

询问有两种情况： 是祖先与子孙的关系； 无关系，即他们的子树不相交。如果是前者的关系，那么子孙其实是没用的，问题变成询问祖先子树内有多少种颜色，随便怎么样都能做。

考虑后者，答案有三个组成部分：只在 子树内出现过的颜色+只在 子树内出现过的颜色+分别在 子树内都有一部分的颜色。前两个是和上面相同的问题，只需要处理第三个部分。

考虑一种颜色 对所有询问的贡献，令 为 最深的 包含了所有颜色为 的节点 的两个节点，即颜色 只在 的子树内出现过，且 各占一部分，显然这样的两个点可能不存在，如果存在那么一定是唯一的。

令 表示 的 ，对于一个询问 ，假如 分别在 ~ ， ~ 路径上（不包括 ），那么颜色 就可以对 产生贡献。

对于每个颜色求出这样一对链，那么接下来要求的就是每组询问在多少对链上，这个可以用树上差分 树状数组来实现。而求这一对链，我是构造了这种颜色的虚树，然后直接看根节点是否只有恰好两个儿子。我个人觉得这样比较方便，验题人的方法是：令 表示颜色为 所有点中， 序最小和最大的两个，然后考虑从这两个点往上倍增。这部分就看个人喜欢了。