P14370 [JOISC 2018] 最差的记者 3 / Worst Reporter 3 Solution
P14370 [JOISC 2018] 最差的记者 3 / Worst Reporter 3Solution
注意：我个人推荐 LibreOJ 题面，看这份的样例图片会好不止亿点点。
前言
在考场上只拿了12 1212分（只想出了Subtask 2）QwQ，大佬勿喷！
这道题纯模拟可以把Subtask 2的分数拿下（因为数据实在太小了），时间复杂度O ( n + q t ) \mathcal{O}(n+qt)O(n+qt)，已经到达10 14 10^{14}1014级别了，肯定爆。
所以我们需要一种算法可以达到O ( n + q ) \mathcal{O}(n+q)O(n+q)（即线性处理），好在它并不困难。
思路
Part I.
我们会发现一件特别有意思的事情。
每个人的移动周期等于单次的移动距离。
其实这就好写了，我们也得到了一个我们需要的线性的方法：递推。
把每个人的移动周期都用f i f_ifi记录下来（0 ≤ i ≤ n 0 \le i \le n0≤i≤n）。
注意给旗手一个f 0 = 1 f_0 = 1f0=1，毕竟它前面没有人（题目已经说了）。
Part II.
第二件有意思的事情。
如果前面的人移动一次后超越了我，那么我就直接跟在他后面，即f i = f i − 1 f_i = f_{i-1}fi=fi−1。
小 L：如果我慢悠悠地移动咋办呢？
那么前面的人走⌈ d i f i − 1 ⌉ \lceil \frac{d_i}{f_{i-1}} \rceil⌈fi−1di⌉次后我再跑，那么f i = f i − 1 × ⌈ d i f i − 1 ⌉ f_i = f_{i-1} \times \lceil \frac{d_i}{f_{i-1}} \rceilfi=fi−1×⌈fi−1di⌉。
其实做到这里状态转移就已经推完了。
总结一下，这个状态转移其实就是
f ( x ) = { f i = f i − 1 ( d i ≤ f i − 1 ) f i = f i − 1 × ⌈ d i f i − 1 ⌉ ( d i ≥ f i − 1 ) f(x)=\left\{ \begin{aligned} f_i & = f_{i-1} & (d_i \le f_{i-1}) \\ f_i & = f_{i-1} \times \lceil \frac{d_i}{f_{i-1}} \rceil & (d_i \ge f_{i-1}) \\ \end{aligned} \right.f(x)=⎩⎨⎧fifi=fi−1=fi−1×⌈fi−1di⌉(di≤fi−1)(di≥fi−1)
Part III.
不过我们发现f i f_ifi（0 ≤ i ≤ n 0 \le i \le n0≤i≤n）会有很多是一样的，于是直接把他的左端点记录下来。
小 L：那么怎么处理这些呢？你是不是要一个时间复杂度低一点的算法？
我们发现它们都是倍增的（至少是2 22倍关系），所以可以直接把复杂度降到O ( log V ) \mathcal{O}(\log V)O(logV)级别。
然后再和{ l , r } \{l, r\}{l,r}取交集就可以了。
贴两段比较没用的代码。
if(d[i]<=dp[i-1]){dp[i]=dp[i-1];le[i]=le[i-1];}else{dp[i]=((d[i]-1)/dp[i-1]+1)*dp[i-1];le[i]=i;}// 不懂的看上面去 :)while(pos>=0){intx=t/dp[pos]*dp[pos];ans+=max(0ll,min(r,-1ll*le[pos]+x)-max(l,-1ll*pos+x)+1);pos=le[pos]-1;}QwQ，绿题拿下！
后记
请勿抄袭题解，违者可能被洛谷棕名哦。