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

• 样例输入

• 3 2 8 7 3 9 1 10 6 1 3 8 1 2

  1 2 3 4 5 6

  3 2 8 7 3 9 1 10 6 1 3 8 1 2

  样例输出

• 数据规模与约定

存在 \(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)\) 。