牛客挑战赛39

A - 聚会

容易想到，两个传送门放在不同半轴肯定不如放在同一半轴好，所以其中一个门肯定是放在处的；
设为正半轴上的朋友们的坐标，为负半轴上的朋友们的坐标；
设为另一个门放在正半轴时，正半轴的朋友全都走到处需要的时间；
设为另一个门放在负半轴时，负半轴的朋友全都走到处需要的时间；
那么答案即为

怎么求和？

考虑二分答案，以正半轴为例，假设为正半轴上距离处最远的朋友的坐标(即)：

• 首先二分得到一个，

• 若对任意，均满足和中的至少一个，则，

• 否则。

负半轴的做法类似。

Code: here

B - 密码系统

先将复制一遍连在后面得到()，然后用后缀数组求得的sa，基于sa求出后缀的rank。

把~按的值分组，利用求得的rank找到每组中最大的后缀。

再利用rank找到答案即可。

感觉说的全是废话。

Code: here

C - 牛牛的等差数列

不考虑取模的部分的话，这个题就是一个人尽皆知的线段树模板题。

每个节点的lazy标记存两个值、，分别为等差数列的首项和公差，利用等差数列求和公式，就能维护区间和了。

如何解决取模的问题？

1. 维护时的结果，输出时再模即可。
2. 因为不取模时最大结果小于，所以直接用int128存，输出时再取模。

Code:here

D - 牛牛的数学题

真超级套娃。

首先对和做一次子集卷积(FMT或FWT)，存到中。

然后对和做一次多项式乘法(NTT)，存到中。

再对和做一次位运算卷积(FWT)，存到中。

询问时输出即可。

Code:here