#3. 大偷儿子,小偷爸爸(原创,还只有第一版题目描述)

大偷儿子,小偷爸爸(原创,还只有第一版题目描述)

当前没有测试数据。

题目背景

sht:我有一个绝佳的idea,可以出一道题:

题目描述 1

大偷儿子,小偷爸爸

大偷儿子和小偷爸爸正在玩游戏 有一个长度为 nn 的数组 AA 和一个长度为 mm 的数组 BB,在此基础上定义一个大小为 n×mn \times m 的矩阵 CC,满足 Cij=Ai×BjC_{i j} = A_i \times B_j。所有下标均从 11 开始。

一共会有 qq 次操作。在每一次游戏中,会事先给出 44 个参数 l1,r1,l2,r2l_1, r_1, l_2, r_2,满足 1l1r1n1 \le l_1 \le r_1 \le n1l2r2m1 \le l_2 \le r_2 \le m

游戏中,大偷儿子先选择一个 l1r1l_1 \sim r_1 之间的下标 xx,然后小偷爸爸选择一个 l2r2l_2 \sim r_2 之间的下标 yy。定义这一轮游戏中二人的得分是 CxyC_{x y}

大偷儿子的目标是使得这个得分尽可能大,小偷爸爸的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家,每次都会采用最优的策略。

请问:按照二人的最优策略,每轮游戏的得分分别是多少?

sht:第一次写出800+字的作文

yuantiji.ac仙人:和P8818 [CSP-S 2022] 策略游戏重题。

sht:那就加单点修改为x的操作

数据结构仙人:树套树秒了,红题都比你这难

sht:那就改成区间修改为x

数据结构仙人:一眼树套树还是可以做,和红题擦边

sht:缩小空间限制,卡树套树

分块仙人:一眼题,分块维护凸包,和P4118一样的思路,刚刚好红题

sht:你想打就打吧,700多行代码

珂学家:珂朵莉树加特判

sht:那就改成区间加

毒瘤指令集优化仙人:一眼题,在P4117中指令集优化可以O(nm)过n=1e6,m=5e5;这题包可以过的啊。暴力更和红题擦不上边了啊

sht:\dots

输入格式

第一行输入三个正整数 n,m,qn, m, q,分别表示数组 AA,数组 BB 的长度和操作次数数。

第二行:nn 个整数,表示 AiA_i,分别表示数组 AA 的元素。

第三行:mm 个整数,表示 BiB_i,分别表示数组 BB 的元素。

接下来 qq 行,有如下操作:

  1. 询问: 1 l1 r1 l2 r21~l_1~r_1~l_2~r_2 表示这一次游戏的 l1,r1,l2,r2l_1, r_1, l_2, r_2
  2. 修改: 2 ch l r x2~ch~l~r~xch=Ach = A 表示给 AAllrr 加上 xx,若 ch=Bch = B 表示给 BBllrr 加上 xx,

输出格式

对于每个询问,输出一行一个整数,分别表示每一轮游戏中,大偷儿子和小偷爸爸在最优策略下的得分。