H-坐火车_2020牛客寒假算法基础集训营4

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛是一名喜欢旅游的同学，在来到渡渡鸟王国时，坐上了颜色多样的火车。

牛牛同学在车上，车上有 $n$ 个车厢，编号为 $1$ 到 $n$ 。每一个车厢有一种颜色，记为 ${\rm col}_i$ 。

他想知道，对于每一个车厢 $x \in [1,\ n]$ ，集合 $\{ (i,j)\ |\ i < x < j,\ l_x \le col_i = col_j \le r_x \}$ 中包含多少个元素。即求解其两边有多少对颜色相同的车厢 $(i,j)$ ，满足这一对车厢的颜色 ${\rm col}_i,{\rm col}_j$ 在 l_x到 r_x 之间。

输入描述:

第一行一个正整数n。
第二行连续输入 n 个三元组，第  个三元组包括三个正整数 (col_i, l_i, r_i)，表示第 节车厢的颜色、颜色限制。输入中没有括号，这 3n 个正整数之间均只用空格隔开，详见样例。

输出描述:

输出一行 n 个非负整数代表答案。

示例1

输入

复制

5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

复制

0 3 4 3 0

备注:



本题已于下方时间节点更新，请注意题解时效性：
1. 2025-11-06 优化题面。