← 返回题目列表

Codeforces · 627/B

B. 工厂维修

中文机器翻译题面 查看原题

一家工厂批量生产顶针。通常,它每天最多可以生产顶针。但由于部分机器存在缺陷,目前每天只能生产b个顶针。工厂打算选择k天的时间段进行维护和施工;在此期间它无法生产任何顶针,但在 k 天结束后将恢复到每天生产 1 个顶针。

最初,没有待处理的订单。工厂收到 di, ai 表格的更新,表明已在第 di 天下了 ai 新订单。每个订单都需要在指定日期精确生产一个顶针。工厂可以选择在单批次中满足任意数量的订单。

当订单进来时,工厂主想知道如果他在给定的 pi 日开始维修,他能够满足的最大订单数量。帮楼主解答疑问。

输入

第一行包含五个整数 n、k、a、b 和 q (1 ≤ k ≤ n ≤ 200 000、1 ≤ b < a ≤ 10 000、1 ≤ q ≤ 200 000)——分别是天数、修复时间长度、工厂生产率和更新次数。

接下来的 q 行包含查询的描述。每个查询都采用以下两种形式之一:

- 1 di ai (1 ≤ di ≤ n, 1 ≤ ai ≤ 10 000),代表di日ai订单的更新,或
- 2 pi (1 ≤ pi ≤ n - k + 1),代表一个问题:目前,如果工厂决定在pi日开始维修,可以完成多少订单?

保证输入至少包含一个第二类型的查询。

输出

对于第二种类型的每个查询,打印一行包含一个整数 - 工厂在所有 n 天内可以满足的最大订单数。

示例

输入 #1

5 2 2 1 8
1 1 2
1 5 3
1 2 1
2 2
1 4 2
1 3 2
2 1
2 3

输出 #1

3
6
4

输入 #2

5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2

输出 #2

7
1

注意

考虑第一个样本。

目前我们每天最多生产 1 个顶针,维修后每天将生产最多 2 个顶针。维修需要2天时间。

第一个问题,我们第1天可以成交1个订单,第2天和第3天因为正在维修所以没有订单,第4天因为当天没有订购顶针所以没有订单,第5天因为我们的产能限制有2个订单,总共完成了3个订单。

对于第三个问题,我们可以在第 1 天填写 1 个订单,在第 2 天填写 1 个订单,在第 5 天填写 2 个订单,总共 4 个订单。