求最大的\(f(1,x)\)。
\(1\leq n\leq 2\times 10^5,1\leq a_i\leq 10^{13}\)

解题思路

考虑到最优解中我们肯定存在某次取模\(a_i\)后得到的是\(a_i-1\)，不然全部加\(1\)肯定更优。那么同样的每个前缀的最优答案都满足如下性质。

拿第一次来距离，就是说\([0,a_1)\)中最优的是\(a_1\)，由于答案递减，那么还没有减去的值（目前的\(x\)）可能影响到后面的状态，那么我们考虑维护\(f_{i,j}\)表示目前的\(x=j\)时已经被膜去的值贡献为\(f_{i,j}\)，也就是答案目前为\(i\times j+f_{i,j}\)。

那么这个转移来说我们就可以大胆地有\(f_{i,j}=max\{f_{i,k}\}(k\geq j)\)了，也就是开始时可以设\(f_{i,a_1-1}=1\)，会发现这样来转移的话最多只有\(n\)个有用的值（前缀最大）。

转移的时候统计上减少的值对前面的贡献即可，用一个\(map\)存下所有的有用位置和值进行转移就好了，因为一个数字被模之后至少减少一半所以一个数字操作次数为\(\log a_i\)次。

时间复杂度：\(O(n\log n\log a_i)\)

code

#include
#include
#include
#include