题解：P4203 [NOI2008] 糖果雨
luoguhandongheng
·
·
题解
这题为啥要坐标变换......
首先云朵颜色没啥用，实际上是直接数给定区间内的云朵数量。云朵的运动周期为 2 \times len。如果记一个云朵左端点到达左端 0 的时刻为 x（模 2 \times len 意义下），长度为 y，那么云朵的运动轨迹可以很好地表示出来。
考虑一个询问 (t_i, l_i, r_i)，先看此时云朵 (x,y) 运动到了哪里。这里要分 t_i \ge x 和 t_i < x 两种情况。\
先讨论 t_i \ge x 的情况，再分两种。当 t_i - x \le len 时，此时云朵左端点的位置就是 t_i - x，那么云朵所代表的线段为 [t_i - x, t_i - x + y]。由题意知，要求云朵线段与询问线段有交集，那么 t_i - x \le r_i 并且 t_i - x + y \ge l_i。解一下得：
\begin{cases} t_i \ge x \ge \max\{t - len, t - r_i\} \\ y - x \ge l_i - t \end{cases}
当 t_i - x > len + 1 时，云朵左端点的位置变成了 2 \times len - (t_i - x) 其他就跟上面一样了。然后 t_i < x 的情况也是一样，自己画图讨论一下就行。
最后四种情况解出来，就变成了一个动态二维数点问题，这题就做完了。复杂度是 O(n \log^2(len))。
Code.