YZOJ P2967 收割
时间限制:4000MS 内存限制:524288KB
难度:\(7.0\)
-
题目描述
兔有 \(n\) 个甘蔗,兔将它们种成一排。
每天早上,第 \(i\) 个甘蔗会长高 \(a_i\) 米,但如果达到 \(b_i\) 米,就不会继续长高,而是维持在 \(b_i\) 米。
兔收割了 \(m\) 次甘蔗,第 \(i\) 次收割在第 \(t_i\) 天的晚上,他收割了 \([l_i, r_i]\) 中的所有甘蔗。收割后,这些甘蔗的高度变为 \(0\) 米,但第二天还会继续按照原来的规则生长。
请你求出兔每天收割了多少甘蔗。
-
输入格式
第一行 \(n, m\) ;
接下来 \(n\) 行,每一行 \(a_i, b_i\) ;
接下来 \(m\) 行,每一行 \(t_i, l_i, r_i\),保证输入的 \(t_i\) 严格递增。
-
输出格式
输出 \(m\) 行表示兔每次收割的甘蔗的高度之和。
-
样例输入
-
1234563 28 73 91 106 1 38 1 2
样例输出
1 2 |
22 13 |
-
数据规模与约定
存在 \(30\%\) 数据,保证所有甘蔗都不会长到 \(b_i\) 米;
存在 \(30\%\) 数据,保证每次收取的是所有萝卜;
存在 \(60\%\) 数据,\(n \leq 50000\);
对于所有数据 \(n \leq 300000\) ,\(m \leq 100000\) ,\(t_i,a_i,b_i \leq 10^9\) 。