#2187. T2

    ID: 2187 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1645来源:qoj.ac数据:公开样例堆

T2

T2

题目描述

标题: T2 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 T 在玩黄金矿工。

为了简化问题,我们假设矿工位于数轴原点,初始时有 n 块金子,且每块金子都位于数轴的正半轴上。第 i 块金子的坐标为 xi,价值为 vi。保证序列 xi 严格递增。获得第 i 块金子所需的时间为 xi⋅vi。注意:与原版游戏不同,矿工可以花 xi⋅vi 的时间直接获得某块金子,而不需要把它前面的金子先清理掉。

小 T 想知道在时限内能获得的金子价值之和最大是多少。但关卡有很多,每次通关后,金子以及时限会发生一些变化。具体来说,共有 m 次操作,操作有以下两种。

  1. 删除第 y 块金子,保证该金子之前没被删除过。
  2. 询问在有 k 个单位时间时,获得金子的价值之和最大是多少。注意:每块金子每次询问只能获得一次,且询问之间独立。也就是说,这次获得的金子在之后的询问中依然会出现。

你能帮小 T 在每个关卡都获得理论最高的价值吗?

输入格式

第一行三个整数 n,m,kmax,分别表示初始金子数,操作数和时限的上界。

第二行到第 n+1 行,每行两个正整数 xi,vi,表示第 i 块金子的位置和价值。

第 n+2 行到第 n+m+1 行,每行两个正整数,形如 1 y 或 2 k,表示一次操作。

输出格式

对于每个询问操作,输出一行一个整数表示答案。

样例输入 1

3 8 50
3 3
4 2
6 4
2 25
2 8
2 7
2 12
1 2
2 25
1 3
2 40

样例输出 1

5
2
0
3
4
3

样例解释

对于第 1 个询问,最佳方案是获得第 1 块金子和第 2 块金子,总用时为 3⋅3+4⋅2=17≤25,总价值为 3+2=5。

对于第 2 个询问,最佳方案是获得第 2 块金子,总用时为 8,总价值为 2。

对于第 3 个询问,最佳方案是什么也不做,总用时为 0,总价值为 0。

对于第 4 个询问,最佳方案是获得第 1 块金子,总用时为 9,总价值为 3。

对于第 5 个询问,由于第 2 块金子已被删除,最佳方案是获得第 3 块金子,总用时为 24,总价值为 4。

对于第 6 个询问,由于第 2 块金子和第 3 块金子均已被删除,最佳方案是获得第 1 块金子,总用时为 9,总价值为 3。

数据范围

对于所有数据,1≤n≤kmax≤2×106,1≤xi⋅vi≤kmax,1≤x1<x2<⋯<xn≤kmax,1≤m≤5000,1≤k≤kmax。

子任务 1(11 分):n,kmax≤5000。

子任务 2(13 分):m=1。

子任务 3(15 分):n≤5000。

子任务 4(21 分):n,kmax≤3×105。

子任务 5(40 分):无特殊限制。

提示

本题的输入量较大,请使用较快的输入方式。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 8 50
3 3
4 2
6 4
2 25
2 8
2 7
2 12
1 2
2 25
1 3
2 40
5
2
0
3
4
3