CF685D Kay and Eternity

白雪女王要求 Kay 用冰块拼出一个单词“eternity”。Kay 渴望完成这项任务，因为这样他就能获得自由，而白雪女王则会把整个世界和一双冰鞋送给他。 在白雪女王的宫殿后面有一块无限大的由格子组成的平原。平原上分布着 $n$ 块冰，每块冰正好占据一个格子，没有两块冰位于同一个格子。为了评估任务的难度，Kay 会观察一些 $k \times k$ 大小的正方形区域，这些正方形的顶点恰好位于格子的顶点上，并且其边平行于坐标轴，他会统计每个正方形内部包含了多少块冰。 这种方法可以用来评估平原某些局部区域的难度。但 Kay 还希望评估整体的难度，因此他设计了如下准则：对于每个 $x$（$1 \leq x \leq n$），他希望统计有多少个 $k \times k$ 的正方形恰好包含了 $x$ 块冰。 请你帮助 Kay 估算白雪女王这项任务的总难度。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100000$，$1 \leq k \leq 300$），分别表示冰块的数量和正方形的边长。接下来的 $n$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$-10^{9} \leq x_{i}, y_{i} \leq 10^{9}$），表示第 $i$ 块冰所在的单元格的坐标。保证任意两块冰的坐标都不同。

输出 $n$ 个整数：第 $i$ 个数表示有多少个 $k \times k$ 的正方形正好包含了 $i$ 块冰，$i$ 从 $1$ 到 $n$。

由 ChatGPT 5 翻译