【推导】【模拟】AtCoder Regular Contest 082 F

题意:有个沙漏,一开始bulb A在上,bulb B在下,A内有a数量的沙子,每一秒会向下掉落1。然后在K个时间点ri,会将沙漏倒置。然后又有m个询问,每次给a一个赋值ai,然后询问你在ti时刻,bulb A的沙子数。保证A和B的总沙子数为X。

函数ft(x)表示t时刻,初始bulb A中的沙子数为x时,当前的bulb A中的沙子数是多少。

最开始时函数恰好为f(x)=x。

然后在第一次翻转之前,函数会逐渐向下移动变为<2>的样子,然后在翻转之后,函数又会逐渐向上移动,直至变成<3>、<4>的样子。但是不论怎样移动,上界一定是X,下界一定是0。

于是按照时间去模拟维护这个分段函数即可,分段函数很简单,最多只有两个转折点。

不过时间范围很大,要离散时间。

原文地址:https://www.cnblogs.com/autsky-jadek/p/7469390.html