QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: alpha1022

Posted at: 2026-01-28 02:35:02

Last updated: 2026-01-28 02:35:05

Back to Problem

题解

简要题意.

给定二维平面上 $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$ 的射线加,矩形查询。

容易转化为二维偏序。

Comments

No comments yet.