QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 8354. T2

Statistics

小 T 在玩黄金矿工。

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

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

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

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

输入格式

第一行三个整数 $n,m,k_{\max}$,分别表示初始金子数,操作数和时限的上界。

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

第 $n+2$ 行到第 $n+m+1$ 行,每行两个正整数,形如 1 y2 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\cdot 3+4\cdot 2=17 \leq 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\leq n\leq k_{\max}\leq 2\times 10^6$,$1\leq x_i\cdot v_i\leq k_{\max}$,$1\leq x_1 < x_2 < \cdots < x_n\leq k_{\max}$,$1\leq m\leq 5000$,$1\leq k \leq k_{\max}$。

子任务 $1$($11$ 分):$n, k_{\max}\leq 5000$。

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

子任务 $3$($15$ 分):$n\leq 5000$。

子任务 $4$($21$ 分):$n, k_{\max}\leq 3\times 10^5$。

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

提示

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