科 学 题
题面
思路
本题偏向思维吧,需要注意一点,开始时所有云都是没有重叠面积且速度相同的,所以往同一方向的云都是相对静止的,并且云的速度方向只有向右和向上,这样就给了我们一个十分优秀的性质—只有向上与向右的云才会重叠,并且最多一个位置只能被两朵云覆盖,最少一朵云,所以只需要判断任意一朵的向右的云是否将会与向上的相交即可,设向右的云有$n$朵,向上的云有$m$朵,那么$n*m$的做法已经不难想出了,但明显是无法拿满分的,需要优化。这时我们或许会想起初中科学老师的教导相对运动这一概念,我们把向上的云固定住,向右的云就变成了向右下$45度$角运动,这样它的右上角和左下角会与$x$轴有交点,然后我们对于一种方向的云他的右上角和左下角的连线映射到$x$轴上,然后对另一种方向的云判断是否有一条线段会与它重叠即可,可以用差分,线段树,排序,二分做。在这里我用的是标记永久化线段树。
细节
因为边缘不算,所以要对一种运动的矩形的对角线在$x$轴上左开右开,对另一种运动的矩形的对角线的查询要左闭右闭,然后离散化。
代码
个人觉得这篇题解写得不大好,还望各位通过代码理解。
1 | // luogu-judger-enable-o2 |