CF1621B · Integers Shop

• 难度：1500
• 标签：data structures、greedy、implementation
• 链接：https://codeforces.com/problemset/problem/1621/B
• 时间限制：2 seconds　内存限制：256 megabytes
• 出现位置：Day03-贪心证明-排序-交换论证/选做

中文题意

整数商店出售 $n$ 个区间。第 $i$ 个区间包含从 $l_i$ 到 $r_i$ 的所有整数，售价为 $c_i$ 枚硬币。

明天 Vasya 会去商店买一些区间。他将得到所买区间中至少出现在一个区间里的所有整数。购买的总花费是所买所有区间的费用之和。

购物之后，Vasya 还会额外获得一些整数作为赠品。当且仅当满足以下所有条件时，他会把整数 $x$ 作为赠品获得：

• Vasya 没有买到 $x$；
• Vasya 买到了某个小于 $x$ 的整数 $l$；
• Vasya 买到了某个大于 $x$ 的整数 $r$。

Vasya 只会把整数 $x$ 作为赠品获得一次，因此获赠后不会出现重复的整数。

例如，若 Vasya 以 $20$ 枚硬币买下区间 $[2, 4]$、以 $22$ 枚硬币买下区间 $[7, 8]$，他共花费 $42$ 枚硬币，从这些区间得到整数 $2, 3, 4, 7, 8$，还会得到赠品 $5$ 和 $6$。

由于技术原因，明天商店里只有前 $s$ 个区间（即区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s]$）可用。

Vasya 想（通过购买或获赠）得到尽可能多的整数。若有多种方式可以做到，他会选择最便宜的一种。

对每个从 $1$ 到 $n$ 的 $s$，求出如果只有前 $s$ 个区间可用，Vasya 将花费多少枚硬币。

输入格式（中文）

本题包含 $t$ 组测试数据。第一行为单个整数 $t$（$1 \leq t \leq 1000$）——测试数据组数。

每组数据第一行为单个整数 $n$（$1 \leq n \leq 10^5$）——商店中区间的数量。

接下来 $n$ 行，每行三个整数 $l_i$、$r_i$、$c_i$（$1 \leq l_i \leq r_i \leq 10^9$，$1 \leq c_i \leq 10^9$）——第 $i$ 个区间的两端与费用。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式（中文）

对每组数据输出 $n$ 个整数：其中第 $s$ 个（$1 \leq s \leq n$）表示如果只有前 $s$ 个区间可用，Vasya 将花费的硬币数。

样例

样例 1

输入：

3
2
2 4 20
7 8 22
2
5 11 42
5 11 42
6
1 4 4
5 8 9
7 8 7
2 10 252
1 11 271
1 10 1

输出：

20
42
42
42
4
13
11
256
271
271