简要题意.
给定二维平面上 $N$ 个矩形,有 $M$ 次移动操作,每个移动操作是给定 $d$,将某个矩形移动 $\{-d,0,d\}^2 \setminus \{(0,0)\}$ 八种方向之一。
移动时会留下轨迹,即留下 $d$ 个矩形。 接下来 $Q$ 次询问某个点被多少个矩形覆盖。$N,M,Q,x,y \le 2.5 \times 10^5$。
差分,转化为水平射线、垂直射线、和 $x$ 轴成 $45^\circ$ 或 $135^\circ$ 的射线加,矩形查询。
容易转化为二维偏序。
Type: Editorial
Status: Open
Posted by: alpha1022
Posted at: 2026-01-28 02:35:02
Last updated: 2026-01-28 02:35:05
简要题意.
给定二维平面上 $N$ 个矩形,有 $M$ 次移动操作,每个移动操作是给定 $d$,将某个矩形移动 $\{-d,0,d\}^2 \setminus \{(0,0)\}$ 八种方向之一。
移动时会留下轨迹,即留下 $d$ 个矩形。 接下来 $Q$ 次询问某个点被多少个矩形覆盖。$N,M,Q,x,y \le 2.5 \times 10^5$。
差分,转化为水平射线、垂直射线、和 $x$ 轴成 $45^\circ$ 或 $135^\circ$ 的射线加,矩形查询。
容易转化为二维偏序。