Codeforces Round #745 (Div. 2) Train Maintenance 题解 (Java/C++)

题解

首先，我们几乎可以立刻注意到如果x[i]>m，那么这个一定没有任何影响，我们可以直接忽略他。于是x[i]的取值范围就从原先的0~$10^9$降低为了0~$2\cdot 10^5$。

进一步如果x[i]<$2\cdot 10^5$且x[i]+y[i]>m。对于这种情况就很清楚，从加i被加进来开始，自x[i]之后，答案永久的加1（除非被移除）。
因此可以自然的想到，仿照括号配对问题的方式，在now+x[i]处标记+1，now+x[i]+y[i]处标记-1，再用一个sum记录当前时间+1和-1的总和。

其实上面做法已经能够覆盖x[i]+y[i]较大的情况了，因为如果x[i]+y[i]较大我们只需要重复$\frac m {x[i]+y[i]}$次标记即可。
但如果x[i]+y[i]非常小（比如2）就需要做$\frac m 2$次标记。因此是$m^2$的时间复杂度。

而对于x[i]+y[i]非常小的情况，以2为例，其实就只取决于i被添加的时间。同理对于x[i]=1，y[i]=2时，我们只需要根据（now-添加时间）%3的值就能知道当前时间i是否在维护。

因此我们以$\sqrt m \approx 450$为界，大于450的按括号配对的方式做，小于450的用取余的方式做即可。

代码

Java

C++