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

Submission #130902600 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #130903537 - Codeforces
Codeforces. Programming competitions and contests, programming community