A14589 | Two Arrays
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given two integer arrays of length $N$ , $A1$ and $A2$ . You are also given $Q$ queries of 4 types:
1 k l r x: set $Ak_i:=min(Ak_i, x)$ for each $l \leq i \leq r$ .
2 k l r x: set $Ak_i:=max(Ak_i, x)$ for each $l \leq i \leq r$ .
3 k l r x: set $Ak_i:=Ak_i+x$ for each $l \leq i \leq r$ .
4 l r: find the $(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$ where $F(k)$ is the $k$ -th Fibonacci number ( $F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$ ), and $x \% y$ denotes the remainder of the division of $x$ by $y$ .
You should process these queries and answer each query of the fourth type.
1 k l r x: set $Ak_i:=min(Ak_i, x)$ for each $l \leq i \leq r$ .
2 k l r x: set $Ak_i:=max(Ak_i, x)$ for each $l \leq i \leq r$ .
3 k l r x: set $Ak_i:=Ak_i+x$ for each $l \leq i \leq r$ .
4 l r: find the $(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$ where $F(k)$ is the $k$ -th Fibonacci number ( $F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$ ), and $x \% y$ denotes the remainder of the division of $x$ by $y$ .
You should process these queries and answer each query of the fourth type.
输入格式
The first line contains two integers $N$ and $Q$ . ( $1 \leq N, Q \leq 5 \times 10^4$ )
The second line contains $N$ integers, array $A1_1, A1_2, \dots A1_N$ . ( $0 \leq A1_i \leq 10^6$ )
The third line contains $N$ integers, array $A2_1, A2_2, \dots A2_N$ . ( $0 \leq A2_i \leq 10^6$ )
The next $Q$ lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. ( $k \in \{1, 2\}$ , $1 \leq l \leq r \leq N$ )
For queries of type 1 and 2, $0 \leq x \leq 10^9$ holds.
For queries of type 3, $−10^6 \leq x \leq 10^6$ holds.
It is guaranteed that after every query each number in arrays $A1$ and $A2$ will be nonnegative.
The second line contains $N$ integers, array $A1_1, A1_2, \dots A1_N$ . ( $0 \leq A1_i \leq 10^6$ )
The third line contains $N$ integers, array $A2_1, A2_2, \dots A2_N$ . ( $0 \leq A2_i \leq 10^6$ )
The next $Q$ lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. ( $k \in \{1, 2\}$ , $1 \leq l \leq r \leq N$ )
For queries of type 1 and 2, $0 \leq x \leq 10^9$ holds.
For queries of type 3, $−10^6 \leq x \leq 10^6$ holds.
It is guaranteed that after every query each number in arrays $A1$ and $A2$ will be nonnegative.
输出格式
Print the answer to each query of the fourth type, in separate lines.
输入输出样例
输入 #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
In the first example: The answer for the first query is $F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$ . After the second query, the array $A2$ changes to $[2, 4, 0]$ . After the third query, the array $A1$ changes to $[0, 0, 0]$ . The answer for the fourth query is $F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$ .
In the second example: The answer for the first query is $F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$ . The answer for the second query is $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$ . After the third query, the array $A1$ changes to $[1, 6, 6, 6, 2]$ . The answer for the fourth query is $F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$ .
In the second example: The answer for the first query is $F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$ . The answer for the second query is $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$ . After the third query, the array $A1$ changes to $[1, 6, 6, 6, 2]$ . The answer for the fourth query is $F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted