题解 AT3527 【[ARC082D] Sandglass】

~~吐槽：怎么只有蓝，ARC 的 F 什么时候才能站起来~~ 这题其实做法挺多的，有正常的 $O(n\log n)$ 做法，也有我同学强行卡过去的 $O(n\log X)$ 做法，这里我提供一个比较巧妙的 $O(n+m)$ 的快很多的线性做法。（$n$ 指翻转次数，$m$ 指询问次数） 首先翻转一次可以看成是沙子从 $A$ 中的沙子数由增加变为减少或者由减少变为增加。 由于沙子总数 $X$ 不变，所以我们可以通过 $A$ 中的沙子数反映 $B$ 中的沙子数。 设 $f_{st}(t)$ 表示初始时 $A$ 中沙子数为 $st$，时间为 $t$ 秒时 $A$ 中剩余的沙子数。 那么我们把时间 $t$ 当为 $x$ 轴，$A$ 中的沙子数当作 $y$ 轴，将初始时 $A$ 中沙子数为 $0\sim X$ 的折线图像画出来：（即 $f_{0\sim X}$ 的图像）  如图，红线为初始时 $A$ 中沙子数为 $X$ 时的折线图像（$f_X$），蓝线为初始时 $A$ 中沙子数为 $0$ 时的折线图像（$f_0$）。 发现不论初始时 $A$ 中有多少沙子，对于任意时刻 $t$，都有 $f_0(t)\leq f_1(t) \leq\cdots \leq f_X(t)$。 那么对于询问 $(t_i,a_i)$，有了 $f_{a_i}(t_i)$ 的上下界 $[f_0(t),f_X(t)]$，就很好做了。 又发现如果折线 $f_{a_i}$ 在某一时刻触碰到了 $f_0$（或者 $f_X$），那么在这个时刻以后，$f_{a_i}$ 的折线就和 $f_0$（$f_X$）重合了。 所以当 $t\leq t_i$ 时，要么折线 $f_{a_i}$ 在 $t\leq t_i$ 的时候触碰到了 $f_0$（$f_X$），此时 $f_{a_i}(t_i)$ 就等于 $f_{0}(t_i)$（$f_{X}(t_i)$）。 要么折线 $f_{a_i}$ 在 $t\leq t_i$ 的时候没有触碰过 $f_0$ 或 $f_X$，那这种情况怎么计算呢？ 发现若 $f_{a_i}$ 触碰了 $f_0$ 或 $f_X$（不妨设触碰了 $f_0$，触碰到 $f_X$ 是同理的），肯定是在 $y=0$ 或 $y=X$ 的时候碰到的，因为只有当 $f_0$ 横着走，$f_{a_i}$ 斜着走的时候他们才会相遇，且只有当 $f_0=0$ 或 $f_0=X$ 的时候 $f_0$ 才会横着走。 所以当 $t\leq t_i$ 时，若 $f_{a_i}$ 没有触碰过 $f_0$ 或 $f_X$，那么折线 $f_{a_i}$ 就肯定没有触碰过 $y=0$ 或 $y=X$，也就是说，不存在任意一个时刻 $t$（$t\leq t_i$），使得沙漏 $A$ 或 $B$ 中没有沙子。 ~~那这个时候我让你求 $\sout{f_{a_i}(t_i)}$ 不是sb题吗~~ 统计一下 $sum$，然后加上 $a_i$ 就好了（详见代码）。 那么现在问题来了：如何判断 $f_{a_i}$ 是否触碰 $f_0$ 或 $f_X$？ 其实很简单，我们先设此时 $f_0$ 答案为 $down=f_0(t_i)$，$f_X$ 答案为 $up=f_X(t_i)$，那么此时答案的上下界为 $[down,up]$。假设 $f_{a_i}$ 没有触碰过 $f_0$ 或 $f_X$ 时用 $sum$ 算出来的答案 $tmp$。 然后如果 $tmp>up$，答案就是 $up$；如果 $tmp<down$，答案就是 $down$；否则答案就是 $tmp$。 因为如果你用 $sum$ 算出来的折线某一时刻超过了 $y=0$ 或 $y=X$，那么它永远不可能回到区间 $[down,up]$，除非此时 $down=up$。 那么我们只用维护 $3$ 个值，就可以维护所有值的范围了：$f_0$、$f_X$、$sum$。 由于给出的 $r_i$ 和 $t_i$ 是递增的，所以可以在 $O(n+m)$ 的时间内维护。 ~~否则加个排序就要带个 $\sout{\log n}$ 了。~~ 代码如下： ```cpp #include<bits/stdc++.h> #define N 100010 using namespace std; int x,n,m,r[N]; int main() { scanf("%d%d",&x,&n); for(int i=1;i<=n;i++) scanf("%d",&r[i]); scanf("%d",&m); int up=x,down=0,sum=0,tmp=0,tag=-1; while(m--) { int t,a; scanf("%d%d",&t,&a); while(tmp<n&&r[tmp+1]<=t) { down=min(x,max(0,down+tag*(r[tmp+1]-r[tmp]))); up=min(x,max(0,up+tag*(r[tmp+1]-r[tmp]))); sum=sum+tag*(r[tmp+1]-r[tmp]); tag=-tag,tmp++; } int down1=min(x,max(0,down+tag*(t-r[tmp]))); int up1=min(x,max(0,up+tag*(t-r[tmp]))); int sum1=sum+tag*(t-r[tmp]); printf("%d\n",min(up1,max(down1,sum1+a))); } return 0; } ```