U618728 「NAPC #1」rStage3 ~ Hard Jump Refreshers

[题解](https://www.luogu.me/article/q4j5740g)。 --- >  > > ——rs6

本题与 [Stage3](https://www.luogu.com.cn/problem/P9431) 的区别为数据范围与询问次数（输入输出格式）不同。 ### 【原始题意】 kid 处于一个无穷大竖直平面内，他在空中时每秒会下落一格（$y$ 坐标减少 $1$），同时在这一秒内他可以选择向左或向右移动一格，或是不改变 $x$ 坐标。 有 $n$ 个位置各异的跳跃球。若 kid 的位置和一个跳跃球重合时，他可以选择跳跃，这会让他上升 $d$ 格（忽略跳跃时间）。可以认为跳跃球是不消耗的，kid 可以在一个跳跃球上重复起跳。kid 不在跳跃球上时无法跳跃。 现对于**每个**跳跃球，询问 kid 从这个跳跃球起跳最多能到达多少个不同的跳跃球。

第一行两个整数 $n,d$。 后 $n$ 行每行两个正整数 $x_i,y_i$ 表示第 $i$ 个跳跃球的位置。保证 $(x_i,y_i)$ 互不相同。

输出一行 $n$ 个正整数，第 $i$ 个整数表示 kid 以第 $i$ 个跳跃球为起点时最大的到达的不同跳跃球的数量。

### 【数据范围】 对于 $10\%$ 的数据（测试点 $1\sim2$），$n\leqslant5000$，$x_i,y_i\leqslant 10^5$。 对于 $100\%$ 的数据，$1\leqslant n\leqslant 10^5$，$0\leqslant d\leqslant 10^8$，$1\leqslant x_i,y_i\leqslant10^8$，$(x_i,y_i)$ 互不相同。 ### 【样例解释】 见 [Stage3](https://www.luogu.com.cn/problem/P9431)。 --- ### Facts 头图原图：