Integers Shop

题意翻译

Vasya 喜欢整数，而正巧的是，他家附近有一个卖整数的商店。这家商店里面有 $n$ 个套餐，第 $i$ 个套餐内含所有在范围 $[l_i,r_i]$ 内的所有整数，花费为 $c_i$。并且这家商店还会赠送更多的整数作为礼物。具体地，如果某消费者在一次购物中没有买整数 $x$，但是在范围 $[0,x)$ 和 $(x,n]$ 内各存在一个该消费者买到的整数，那么该消费者将会收到商店赠送的整数 $x$。Vasya 希望他能买到的整数尽可能多，并且在该前提下，他希望花费尽可能小。 Vasya 计划明天去商店买些整数，但不幸的是，出于某些原因，该商店明天只会卖**前 $s$ 个**套餐，而且 Vasya 并不知道 $s$ 的具体值。于是，他想知道对于范围 $[1,n]$ 内的所有整数 $s$，求出在只卖**前 $s$ 个**套餐时，在买到的整数尽可能多的前提下，最小花费是多少。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 1000$。 - $1\leqslant n\leqslant 10^5$，$\sum n\leqslant 2\times 10^5$。 - $1\leqslant l_i\leqslant r_i\leqslant 10^9$，$1\leqslant c_i\leqslant 10^9$。 Translated by Eason_AC 2022.1.4

题目描述

The integers shop sells $ n $ segments. The $ i $ -th of them contains all integers from $ l_i $ to $ r_i $ and costs $ c_i $ coins. Tomorrow Vasya will go to this shop and will buy some segments there. He will get all integers that appear in at least one of bought segments. The total cost of the purchase is the sum of costs of all segments in it. After shopping, Vasya will get some more integers as a gift. He will get integer $ x $ as a gift if and only if all of the following conditions are satisfied: - Vasya hasn't bought $ x $ . - Vasya has bought integer $ l $ that is less than $ x $ . - Vasya has bought integer $ r $ that is greater than $ x $ . Vasya can get integer $ x $ as a gift only once so he won't have the same integers after receiving a gift. For example, if Vasya buys segment $ [2, 4] $ for $ 20 $ coins and segment $ [7, 8] $ for $ 22 $ coins, he spends $ 42 $ coins and receives integers $ 2, 3, 4, 7, 8 $ from these segments. He also gets integers $ 5 $ and $ 6 $ as a gift. Due to the technical issues only the first $ s $ segments (that is, segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_s, r_s] $ ) will be available tomorrow in the shop. Vasya wants to get (to buy or to get as a gift) as many integers as possible. If he can do this in differents ways, he selects the cheapest of them. For each $ s $ from $ 1 $ to $ n $ , find how many coins will Vasya spend if only the first $ s $ segments will be available.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains the single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the number of segments in the shop. Each of next $ n $ lines contains three integers $ l_i $ , $ r_i $ , $ c_i $ ( $ 1 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9 $ ) — the ends of the $ i $ -th segments and its cost. It is guaranteed that the total sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output $ n $ integers: the $ s $ -th ( $ 1 \leq s \leq n $ ) of them should be the number of coins Vasia will spend in the shop if only the first $ s $ segments will be available.

输入输出样例

输入样例 #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

输出样例 #1

20
42
42
42
4
13
11
256
271
271

说明

In the first test case if $ s = 1 $ then Vasya can buy only the segment $ [2, 4] $ for $ 20 $ coins and get $ 3 $ integers. The way to get $ 7 $ integers for $ 42 $ coins in case $ s = 2 $ is described in the statement. In the second test case note, that there can be the same segments in the shop.