#P16071. [2022国家队训练南京站]黄金矿工

    ID: 15282 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-逆序处理删除根号分治0/1 背包以值为状态倒序更新避免重复使用

[2022国家队训练南京站]黄金矿工

题目描述

小 T 在玩黄金矿工。

为了简化问题,我们假设矿工位于数轴原点,初始时有 nn 块金子,且每块金子都位于数轴的正半轴上。第 ii 块金子的坐标为 xix_i,价值为 viv_i。保证序列 xix_i 严格递增。

获得第 ii 块金子所需的时间为 xi⋅vix_i\cdot v_i。注意:与原版游戏不同,矿工可以花 xi⋅vix_i\cdot v_i 的时间直接获得某块金子,而不需要把它前面的金子先清理掉。

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

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

请你帮助小 T 求出每次询问的最优答案。

输入格式

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

接下来 nn 行,每行两个正整数 xi,vix_i,v_i,表示第 ii 块金子的位置和价值。

接下来 mm 行,每行两个正整数,形如 1 y 或 2 k,表示一次操作。

输出格式

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

样例

输入

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

样例解释

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

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

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

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

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

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

数据范围

对于所有数据:

  • 1≤n≤kmax⁡≤2×1061\le n\le k_{\max}\le 2\times10^6;
  • 1≤xi⋅vi≤kmax⁡1\le x_i\cdot v_i\le k_{\max};
  • 1≤x1<x2<⋯<xn≤kmax⁡1\le x_1<x_2<\cdots<x_n\le k_{\max};
  • 1≤m≤50001\le m\le 5000;
  • 询问中 1≤k≤kmax⁡1\le k\le k_{\max};
  • 删除操作保证对应金子此前没有被删除。

子任务:

子任务 分值 限制
1 11 n,kmax⁡≤5000n,k_{\max}\le 5000
2 13 m=1m=1
3 15 n≤5000n\le 5000
4 21 n,kmax⁡≤3×105n,k_{\max}\le 3\times10^5
5 40 无特殊限制

提示

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