#P14477. [2025年广东省队集训]火力全开

    ID: 13694 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000线段树动态规划分治数据结构贪心

[2025年广东省队集训]火力全开

题目描述

有 nn 个敌人,你有两种攻击他们的方式:

  1. 花费 11 的代价,选择一个敌人,对其进行一次普通攻击。

  2. 使用一颗炮弹,对所有敌人造成一次爆炸。

对于第二种攻击方式,有 mm 颗炮弹可供使用,使用第 ii 颗炮弹需要花费 cic_i 的代价,并造成一次威力为 did_i 的爆炸。每颗炮弹只能使用一次。

对于第 ii 个敌人,如果其被使用第一种攻击方式攻击了 aia_i 次,或者受到了 kk 次威力不小于 bib_i 的爆炸,就会死亡。

有 qq 次修改,每次输入 op,x,y,zop,x,y,z,如果 op=1op=1,表示将 axa_x 修改为 yy,bxb_x 修改为 zz。否则 op=2op=2,表示将 cxc_x 修改为 yy,dxd_x 修改为 zz。每次修改后,求出至少需要花费多少代价,才能使所有敌人死亡。修改之间不独立,也即修改的结果会继承。

输入格式

第一行四个正整数 n,m,q,kn,m,q,k,分别表示敌人个数,炮弹颗数,修改次数,敌人的抗爆属性。

接下来 nn 行,每行两个整数 ai,bia_i,b_i,表示敌人的属性。

接下来 mm 行,每行两个整数 ci,dic_i,d_i,表示炮弹的属性。

接下来 qq 行,每行四个整数 op,x,y,zop,x,y,z,表示一次修改。

输出格式

输出 qq 行,每行一个整数,表示每次修改后的答案。

输入样例1

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

输出样例1

10
16
14

样例 11 解释

第一次修改后,直接选择第一颗炮弹,可以将所有敌人炸死,代价为 1010。

第二次修改后,最优方案是用普通攻击击败所有敌人,代价为 1616。

第三次修改后,使用第二颗炮弹炸掉第一个敌人,再用普通攻击击败第二个敌人,代价为 1414。

数据范围

对于所有数据,1≤n,m,q≤2.5×1051\le n,m,q\le 2.5\times 10^5,1≤k≤1041\le k\le 10^4,qk≤5×105qk\le 5\times 10^5,1≤op≤21\le op\le 2,1≤ai,bi,ci,di,y,z≤1091\le a_i,b_i,c_i,d_i,y,z\le 10^9,如果 op=1op=1,则 1≤x≤n1\le x\le n,否则 1≤x≤m1\le x\le m。

子任务编号 n,m,q≤n,m,q\le 特殊性质 分数
11 200200 无 1010
22 50005000 2020
33 10510^5 op=1op=1
44 k≤10k\le 10
55 2.5×1052.5\times 10^5 无 3030