← 返回题目列表

Codeforces · 1928/F

F. 数字模式

中文机器翻译题面 查看原题

Anya 从事针线活。今天她决定用半透明线编织一条围巾。每个线程都由一个整数来表征——透明度系数。

围巾按照以下方案制作:选择透明度系数为$$$a_1、a_2、\ldots、a_n$$$的水平线和透明度系数为$$$b_1、b_2、\ldots、b_m$$$的垂直线。然后它们如下图所示交织在一起,形成一块大小为 $$$n \times m$$$ 的织物,恰好由 $$$nm$$$ 节点组成:

$$$n = m = 4$$$ 的一块织物示例。

当交织紧密并且线之间没有间隙时,编号为$$$i$$$的水平线和编号为$$$j$$$的垂直线形成的每个节点将变成一个单元,我们将其表示为$$$(i,j)$$$。单元格 $$$(i, j)$$$ 的透明度系数为 $$$a_i + b_j$$$。

生成的围巾的有趣之处在于其子方块$$$^{\dagger}$$$的数量,其中不存在具有相同透明度系数的相邻$$$^{\dagger \dagger}$$$单元对。

Anya 尚未决定将哪些线用于围巾,因此您还将收到 $$$q$$$ 查询来增加/减少某些范围内线的系数。在每个查询之后,您需要输出结果围巾的兴趣度。

$$$^{\dagger}$$$一块织物的子正方形被定义为其所有单元$$$(i, j)$$$的集合,使得对于某些整数$$$x_0 \le i \le x_0 + d$$$和$$$y_0 \le j \le y_0 + d$$$, $$$y_0$$$ 和 $$$d$$$($$$1 \le x_0 \le n - d$$$、$$$1 \le y_0 \le m - d$$$、$$$d \ge 0$$$)。

$$$^{\匕首\匕首}$$$。单元格 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 是相邻的当且仅当 $$$|i_1 - i_2| + |j_1 - j_2| = 1$$$。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$0 \le q \le 3 \cdot 10^5$$$) — 水平线程数、垂直线程数和更改请求数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) - 水平线程的透明度系数,线程从上到下编号。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$-10^9 \le b_i \le 10^9$$$) - 垂直线程的透明度系数,线程从左到右编号。

接下来的 $$$q$$$ 行指定更改请求。每个请求由四元组整数 $$$t$$$、$$$l$$$、$$$r$$$ 和 $$$x$$$ 描述($$$1 \le t \le 2$$$、$$$l \le r$$$、$$$-10^9 \le x \le 10^9$$$)。根据请求中的参数$$$t$$$,需要执行以下操作:

- $$$t=1$$$。 $$$[l, r]$$$ 范围内水平线的透明度系数增加 $$$x$$$(换句话说,对于所有整数 $$$l \le i \le r$$$,$$$a_i$$$ 的值增加 $$$x$$$);
- $$$t=2$$$。 $$$[l, r]$$$ 范围内的垂直线的透明度系数增加 $$$x$$$(换句话说,对于所有整数 $$$l \le i \le r$$$,$$$b_i$$$ 的值增加 $$$x$$$)。

输出

输出 $$$(q+1)$$$ 行。在第 $$$(i + 1)$$$ 行 ($$$0 \le i \le q$$$) 中,输出一个整数 — 应用第一个 $$$i$$$ 请求后围巾的兴趣度。

示例

输入 #1

4 4 0
1 1 2 3
1 2 2 3

输出 #1

20

输入 #2

3 3 2
1 1 1
2 2 8
1 2 3 1
2 2 3 -6

输出 #2

9
10
11

输入 #3

3 2 2
-1000000000 0 1000000000
-1000000000 1000000000
1 1 1 1000000000
2 2 2 -1000000000

输出 #3

8
7
7

注意

在第一个示例中,所得板中单元的透明度系数如下:

2334233434454556

那么有以下子方格不包含具有相同透明度系数的两个相邻单元格:

- 每个 $$$16$$$ 单元格分别;
- 左上角位于单元格 $$$(3, 1)$$$ 且右下角位于单元格 $$$(4, 2)$$$ 的子正方形;
- 左上角位于单元格 $$$(2, 3)$$$ 且右下角位于单元格 $$$(3, 4)$$$ 的子正方形;
- 左上角位于单元格 $$$(2, 1)$$$ 且右下角位于单元格 $$$(3, 2)$$$ 的子正方形;
- 左上角位于单元格 $$$(3, 3)$$$ 且右下角位于单元格 $$$(4, 4)$$$ 的子正方形。

在第二个示例中,在第一次查询之后,水平线程的透明度系数为$$$[1, 2, 2]$$$。第二次查询后,垂直线的透明度系数为$$$[2, -4, 2]$$$。