Problem 2. Grass Segments

USACO 2024 US Open Contest, Gold

Bessie 正在数轴的正半轴上种一些草。她有 $N$（$2\le N\le 2\cdot 10^5$）个不同的栽培品种，并将把第 $i$ 个品种种植在区间 $[\ell_i, r_i]$（$0 < \ell_i < r_i \leq 10^9$）内。

此外，品种 $i$ 会在存在某个品种 $j$（$j\neq i$）使得品种 $j$ 与品种 $i$ 重叠至少 $k_i$（$0 < k_i \leq r_i - \ell_i$）长度时生长得更好。Bessie 想要评估她所有的品种。对于每一个 $i$，计算 $j\neq i$ 的数量，使得 $j$ 与 $i$ 重叠至少 $k_i$ 长度。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

以下 $N$ 行每行包含三个空格分隔的整数 $\ell_i$，$r_i$ 和 $k_i$。

输出格式（输出至终端 / 标准输出）：

输出所有品种的答案，每种一行。

输入样例：

2
3 6 3
4 7 2

输出样例：

0
1

两品种的重叠部分为 $[4,6]$，长度为 $2$，不小于 $2$ 但并非不小于 $3$。

输入样例：

4
3 6 1
2 5 1
4 10 1
1 4 1

输出样例：

3
3
2
2

输入样例：

5
8 10 2
4 9 2
3 7 4
5 7 1
2 7 1

输出样例：

0
3
1
3
3

测试点性质： 测试点 4-5：$N \leq 5000$。测试点 6-11：$k$ 对于所有的区间均相同。测试点 12-20：没有额外限制。 此外，对于测试点 5，7，……，19，对于所有 $i$ 有 $r_i \leq 2N$。

供题：Benjamin Qi