CF1902D 题解

Xy_top · 2024-01-31 20:57:26 · 题解

分块大法好，万物皆可分块！！！

看了一下好像还没有人发，于是我先来水分块做法。

首先，如果不是在 [l,r] 内到达的询问可以直接预处理。

那么在 [l,r] 内到达的可以怎么做呢？考虑分块，首先倒着循环，使用 unordered_map 记录形如 {x,y} 的对子，分别表示块内到某个位置 x 的增加量和 y 的增加量。（可能为负）

因为一个块内的增加量的绝对值是 \sqrt{n} 级别的，于是哈希函数可以设置为 x\times \sqrt{n}+y，本文取 x\times 500 + y。

查询的时候维护当前的点 {x_0,y_0}，找块中有没有 {x-x_0,y-y_0}，这是 O(1) 的，然后跳到下一个块，块外暴力。

总时间复杂度 O(n\sqrt{n} + q\sqrt {n})。