← 返回题目列表

Codeforces · 1599/E

E. 两个数组

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

给定两个长度为 $$$N$$$、$$$A1$$$ 和 $$$A2$$$ 的整数数组。您还会收到 4 种类型的 $$$Q$$$ 查询:

1 k l r x:为每个 $$$l \leq i \leq r$$$ 设置 $$$Ak_i:=min(Ak_i, x)$$$。

2 k l r x:为每个 $$$l \leq i \leq r$$$ 设置 $$$Ak_i:=max(Ak_i, x)$$$。

3 k l r x:为每个 $$$l \leq i \leq r$$$ 设置 $$$Ak_i:=Ak_i+x$$$。

4 l r: 找到 $$$(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$$$ 其中 $$$F(k)$$$ 是第 $$$k$$$ 个斐波那契数 ($$$F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$$$),并且$$$x \% y$$$表示$$$x$$$除以$$$y$$$的余数。

您应该处理这些查询并回答第四种类型的每个查询。

输入

第一行包含两个整数 $$$N$$$ 和 $$$Q$$$。 ($$$1 \leq N, Q \leq 5 \times 10^4$$$)

第二行包含 $$$N$$$ 整数,数组 $$$A1_1, A1_2, \dots A1_N$$$。 ($$$0 \leq A1_i \leq 10^6$$$)

第三行包含 $$$N$$$ 整数,数组 $$$A2_1, A2_2, \dots A2_N$$$。 ($$$0 \leq A2_i \leq 10^6$$$)

接下来的 $$$Q$$$ 行描述查询。每行包含 5 或 3 个整数,其中第一个整数表示查询的类型。 ($$$k \in \{1, 2\}$$$, $$$1 \leq l \leq r \leq N$$$)

对于类型 1 和 2 的查询,$$$0 \leq x \leq 10^9$$$ 成立。

对于类型 3 的查询, $$$−10^6 \leq x \leq 10^6$$$ 成立。

保证每次查询后数组 $$$A1$$$ 和 $$$A2$$$ 中的每个数字都为非负数。

输出

在单独的行中打印第四种类型的每个查询的答案。

示例

输入 #1

3 4
1 0 2
2 1 0
4 1 3
3 2 2 2 3
1 1 1 3 0
4 1 3

输出 #1

4
4

输入 #2

5 4
1 3 5 3 2
4 2 1 3 3
4 1 3
4 2 5
2 1 2 4 6
4 2 4

输出 #2

18
26
68

注意

在第一个示例中:第一个查询的答案是 $$$F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$$$。第二次查询后,数组 $$$A2$$$ 更改为 $$$[2, 4, 0]$$$。第三次查询后,数组 $$$A1$$$ 更改为 $$$[0, 0, 0]$$$。第四个查询的答案是 $$$F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$$$。

在第二个示例中:第一个查询的答案是 $$$F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$$$。第二个查询的答案是 $$$F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26$$$。第三次查询后,数组 $$$A1$$$ 更改为 $$$[1, 6, 6, 6, 2]$$$。第四个查询的答案是 $$$F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$$$。