徐老师的宠物养成plus
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
众所周知，徐老师很喜欢玩 《宝可梦》，并且他很喜欢养鲤鱼王因为鲤鱼王的数量越养越多，他决定开一个大小为 $n * m$ 池塘来专门养鲤鱼王，这个池塘被隔成了 $n * m$ 个格子，每个格子里可以养一只鲤鱼王
现在徐老师准备再次购买 "属性强化果实"，在购买之前他发现了一个更加有效果的道具——"属性强化饲料"，一份饲料可以让一个矩形区间内的鲤鱼王统统受到属性强化
假设一只鲤鱼王从没有受到过强化，当它被强化 $d$ 次以后就会进化成暴鲤龙！
现在徐老师购买了 $c$ 份属性强化饲料，由于他使用饲料的时候手会抖，导致每次能够受到强化的矩阵大小不同，这里我们可以认为徐老师第 $i$ 次使用属性强化饲料时会强化的矩形区间左上角的坐标为 $(x_1,y_1)$，右下角的坐标 $(x_2,y_2)$
接下来需要会需要挑选一些鲤鱼王/暴鲤龙进行组队，为了方便，他制定了如下的组队规则：
1. 以每行为单位，一行内的所有鲤鱼王/暴鲤龙算作一组
2. 设一只宝可梦队伍中有 $A$ 只鲤鱼王，$B$ 只暴鲤龙，该小队的战斗力为 $A * B$
3. 每次询问徐老师会提出两个数字 $a,b$ 作为一次编队，表示需要挑选 $a$ 组，每组中选择 $b$ 只宝可梦组成一队（位置，顺序无关）
现在徐老师想知道，对于每次编队，组成的所有队伍战斗力之和最大是多少？
P.S. 为了方便计算，一开始我们认为池塘里的所有鲤鱼王强化次数均为 $0$
输入格式
输入第一行包含五个整数 $n,m,c,d,q$，含义如题接下来 $c$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$ 表示这一次使用属性强化饲料的矩阵左上角和右下角
接下来 $q$ 行，每行两个整数 $a,b$ 表示一次编队要求
| 数据点编号 | $n,m$ | $c$ | $d$ | $q$ |
| :--------: | :-------: | :---: |:---: |:---: |
| $1 \sim 2$ | $100$ | $300$ | $10$ | $100$ |
| $3 \sim 4$ | $100$ | $1000$ | $10$ | $1000$ |
| $5 \sim 6$ | $3000$ |$300000$| $10$ | $3000$ |
| $7 \sim 8$ | $3000$ |$300000$| $10$ |$300000$|
| $9 \sim 10$ | $n=100000,m=3000$ | $3000$ | $10$ | $300000$ |
| $11 \sim 13$ | $300000$ |$300000$| $1$ |$300000$|
| $14 \sim 16$ | $100000$ |$100000$|依次为$3,6,10$| $300000$ |
| $17 \sim 18$ | $300000$ |$300000$| $10$ | $300000$ |
| $19 \sim 20$ | $300000$ |$300000$| $10$ | $1000000$ |
对于所有的数据，保证 $1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq m, 1 \leq a \leq n, 1 \leq b \leq m$
对于编号为 $17 \sim 20$ 的测试数据时间限制为 $2s$
输出格式
对于每次编队要求，输出该次编队能获得的最大战斗力之和样例
5 5 3 2 5
1 1 4 5
3 1 5 3
1 4 5 4
5 3
4 3
4 2
3 3
2 48
8
4
6
6提示
每只鲤鱼王的强化次数如下：```
1 1 1 2 1
1 1 1 2 1
2 2 2 2 1
2 2 2 2 1
1 1 1 1 0
```
接下来用 $0$ 表示鲤鱼王，用 $1$ 表示暴鲤龙，强化后的池塘内种类如下：
```
0 0 0 1 0
0 0 0 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
```
对于第一次询问 $5,3$，选 $5$ 组，每组选 $3$ 只：
第一、二组选择 $1$ 只暴鲤龙，$2$ 只鲤鱼王，战斗力各为 $1 * 2 = 2$
第三、四组选择 $2$ 只暴鲤龙，$1$ 只鲤鱼王，战斗力各为 $2 * 1 = 2$
第五组只能选择 $3$ 只鲤鱼王战斗力为 $0$
该方案为最大战斗力之和为 $2 + 2 + 2 + 2 + 0 = 8$
对于第五次询问 $2,4$，选 $2$ 组，每组选 $4$ 只：
第一、二组选择 $1$ 只暴鲤龙，$3$ 只鲤鱼王，战斗力各为 $1 * 3 = 3$
第三、四组选择 $3$ 只暴鲤龙，$1$ 只鲤鱼王，战斗力各为 $3 * 1 = 3$
第五组只能选择 $3$ 只鲤鱼王战斗力为 $0$
选 $2$ 组的最大战斗力之和为 $3 + 3 = 6$
23CSP-S秋季提高组模拟赛(4)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-9-30 17:15
- 结束于
- 2023-10-10 17:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 29
