题解：P17112 「FAOI-R13」Hi, story

· · 题解

P17112 题解

《论如何在 15 分钟内不使用高级数据结构通过本题》。

这启示我们，出数据结构题一定要造强数据和小数据。

本题解非正解。

乱搞思路

首先我们先写一个暴力。

然后我们发现在操作 1 不暴力的情况下难以及时获得每个点的 a_i，于是可以用树状数组将操作 1 变成 O(\log n) 区间加 1，这样就可以 O(\log n) 查询每个点的值。具体地，若点 i 的查询结果为 k，即表示这个点被加了 k 个 b_i，则 a_i + k \times b_i 即为点 i 的真实 a_i 值。

但是操作 2 还是很暴力啊，怎么办？

我们发现如果不特意构造数据，那么区间 \gcd 其实不需要查询区间内所有点，只需要随机找足够多的点即可。于是我们只需要设置一个阈值 p，若区间长度 \le p 则暴力整个区间，若区间长度 > p 则随机取 p 个点即可。

当然这样很好卡，比如区间 [1 , n] 有 n - 1 个 6 和 1 个 2，如果随机不到唯一的这个 2，那么我们就只能输出错误的答案 6。

于是可以随意增加一点其它东西，让整个算法更难卡。虽然本题没有这种数据，但是我们可以再增加 ST 表，每次除了随机取点以外，再将区间原来 a_i 最小和最大的位置也拿来做 \gcd。

至于阈值 p，首先需要考虑到全部操作均为询问时的复杂度，故 p \le 200 可以保证不会超时，又因为过多的点没有用，所以我们还可以令 \displaystyle p \le \frac {2 \times 10 ^ 7} q。

赛时抱着乱搞的心态写出这样的代码，不小心就过了。

由于本做法非正解，故不提供代码。