CF56E Domino Principle

Vasya 对摆放多米诺骨牌很感兴趣。他已经厌倦了普通的多米诺骨牌，于是他使用了不同高度的多米诺骨牌。他将 $n$ 个多米诺骨牌放在桌子上，沿一条轴从左到右排列。每个多米诺骨牌垂直于该轴摆放，使得轴穿过其底座的中心。第 $i$ 个多米诺骨牌的坐标为 $x_i$，高度为 $h_i$。现在，Vasya 想知道，对于每一个骨牌，如果将它向右推倒，会有多少个骨牌倒下。请你帮他计算每个骨牌向右推倒时会倒下的骨牌数。 假设只有当骨牌在底座正上方被触碰时才会倒下。换句话说，初始坐标为 $x$，高度为 $h$ 的骨牌倒下后，将会使位于区间 $[x+1, x+h-1]$ 上的所有骨牌全部倒下。 

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示多米诺骨牌的数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $h_i$（$-10^8 \leq x_i \leq 10^8, 2 \leq h_i \leq 10^8$），分别表示每个多米诺骨牌的坐标和高度。任意两个骨牌不会放在同一个坐标点上。

输出 $n$ 个用空格分隔的整数 $z_i$，第 $i$ 个数表示如果将第 $i$ 个骨牌向右推倒（包括它自己），会有多少个骨牌倒下。

由 ChatGPT 5 翻译