YZOJ P2967 收割

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\) 行表示兔每次收割的甘蔗的高度之和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

存在 \(30\%\) 数据,保证所有甘蔗都不会长到 \(b_i\) 米;

存在 \(30\%\) 数据,保证每次收取的是所有萝卜;

存在 \(60\%\) 数据,\(n \leq 50000\);

对于所有数据 \(n \leq 300000\) ,\(m \leq 100000\) ,\(t_i,a_i,b_i \leq 10^9\) 。

 

 

 


 

 

 

首先麻烦的是每个(甘蔗=萝卜)的生长状态都是不一样的,可能有的已经成熟但是有的才刚被收割,直接维护有点麻烦。(其实是我不会)

发现每次操作都会把一段区间内的甘蔗全部收割,也就是生长状态清零,也就是区间推平assign)操作。

都知道区间推平可以使用 ODT 来维护,也就是 std::set 维护上次收割时刻相同的区间,每次操作的时候把 \([l, r]\) 分割split)成若干段分别计算答案,最后再推平即可。

剩下的问题就只有如何求出:生长了一段时间 \(\Delta t\) 后,区间内甘蔗的高度总和。

考虑 \(\lfloor \frac{b_i}{a_i} \rfloor\) ,它代表某一甘蔗成熟的时刻,在这个时刻之前它的高度是 \(\Delta t \cdot a_i\) ,之后它的高度是 \(b_i\) 。

所以可以建立权值线段树,下标表示时刻(不离散化就会跑的跟我一样慢),要找到 \(\Delta t\) 时刻所有在线段树上的甘蔗的生长状态,可以在上面二分查找。

对于区间 \([l, r]\) :若 \(\Delta t \leq mid\) ,那么右区间 \((mid, r]\) 时刻内的甘蔗都没成熟,对 \(QA\) 贡献右区间内 \(a\) 的和,同时递归进左区间处理;若 \(\Delta t > mid\),那么左区间 \([l, mid]\) 时刻内的甘蔗都成熟了,对 \(QB\) 贡献左区间内 \(b\) 的和,同时递归进右区间处理。

特别注意的是 \(l = r = \Delta t\) 的情况,由于 \(\lfloor \frac{b_i}{a_i} \rfloor \leq \frac{b_i}{a_i}\) ,所以都按照未成熟的情况对 \(QA\) 贡献它的 \(a\) 。

所以本次询问的答案就是 \(\Delta t \cdot QA + QB\) 。

因为要求的是某一区间内甘蔗的生长高度和,所以建立主席树(或者说把权值线段树拿去可持久化)即可。

时间复杂度:大概是 \(O((n+m)\log n)\) 。

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注