Little Pony and Lord Tirek
题意翻译
- 维护一个长度为 $n(1\le n \le 10^5)$ 的数组 $s$,初值给定且 $0 \le s_i \le 10^5$。
- 每过 $1$ 单位时间,都会对于所有 $[1,n]$ 之间的整数 $i$,执行 $s_i \gets \min\{m_i,s_i+r_i\}$。其中 $m_i$ 和 $r_i$ 给定且 $0 \le m_i, r_i \le 10^5$。
- 维护 $m(1\le m \le 10^5)$ 次操作,每次操作时会将时间设为 $t(0 \le t \le 10^9)$,并且查询 $s$ 数组 $[l,r]$ 区间和。每次操作结束后会将 $s$ 数组的 $[l,r]$ 区间推平为 $0$,保证 $t_i$ 递增。
- 初始没有进行操作时时间为 $0$。
题目描述
Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series "My Little Pony: Friendship Is Magic". In "Twilight's Kingdom" (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF453E/643ac83a27b2195ea33883fd4f5562486272f6c4.png)The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.
Now to simplify the problem, assume you have $ n $ ponies (numbered from 1 to $ n $ ). Each pony has three attributes:
- $ s_{i} $ : amount of mana that the pony has at time 0;
- $ m_{i} $ : maximum mana that the pony can have;
- $ r_{i} $ : mana regeneration per unit time.
Lord Tirek will do $ m $ instructions, each of them can be described with three integers: $ t_{i},l_{i},r_{i} $ . The instruction means that at time $ t_{i} $ , Tirek will use Absorb Mana on ponies with numbers from $ l_{i} $ to $ r_{i} $ (both borders inclusive). We'll give you all the $ m $ instructions in order, count how much mana Tirek absorbs for each instruction.
输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of ponies. Each of the next $ n $ lines contains three integers $ s_{i},m_{i},r_{i} $ $ (0<=s_{i}<=m_{i}<=10^{5}; 0<=r_{i}<=10^{5}) $ , describing a pony.
The next line contains an integer $ m $ ( $ 1<=m<=10^{5} $ ) — the number of instructions. Each of the next $ m $ lines contains three integers $ t_{i},l_{i},r_{i} $ $ (0<=t_{i}<=10^{9}; 1<=l_{i}<=r_{i}<=n) $ , describing an instruction of Lord Tirek. The instructions are given in strictly increasing order of $ t_{i} $ (all $ t_{i} $ are distinct).
输出格式
For each instruction, output a single line which contains a single integer, the total mana absorbed in this instruction.
输入输出样例
输入样例 #1
5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5
输出样例 #1
25
58
说明
Every pony starts with zero mana. For the first instruction, each pony has 5 mana, so you get 25 mana in total and each pony has 0 mana after the first instruction.
For the second instruction, pony 3 has 14 mana and other ponies have mana equal to their $ m_{i} $ .