308922: CF1599E. Two Arrays
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Two Arrays
题意翻译
### 题目描述 给定两个长度为 $N$ 的整数列,$A1$ 和 $A2$ 。有以下四种操作 : - 操作 $1$: 格式:`1 k l r x` 含义:将第 $k$ 个数列在区间 $[l,r]$ 内的所有数与 $x$ 取 $\min$ 。 - 操作 $2$: 格式:`2 k l r x` 含义:将第 $k$ 个数列在区间 $[l,r]$ 内的所有数与 $x$ 取 $\max$ 。 - 操作 $3$:格式: `3 k l r x` 含义:将第 $k$ 个数列在区间 $[l,r]$ 内的所有数加上 $x$ 。 - 操作 $4$:格式: `4 l r` 含义:输出 $\sum^r_{i=l}F(A1_i+A2_i)$,其中 $F(k)$ 表示第 $k$ 个斐波那契数 $(F(0)=0,F(1)=1,F(k)=F(k-1)+F(k-2))$,输出对 $10^9+7$ 取模 。 ### 输入格式 第一行包含两个整数 $N$ 和 $Q$,分别表示数列的长度和操作数 $(1\leq N,Q\leq 5\times 10^4)$ 。 第二行包含 $N$ 个整数,表示数列 $A1$ 。$(0\leq A1_i\leq 10^6)$ 第三行包含 $N$ 个整数,表示数列 $A2$ 。$(0\leq A2_i\leq 10^6)$ 接下来 $Q$ 行,每行表示一次操作 。$(k\in \{ 1,2\},1\leq l\leq r\leq N)$ 对于操作 $1$ 和 $2$,$0\leq x\leq 10^9$ 。 对于操作 $3$,$-10^6\leq x\leq10^6$ 。 **数据保证在每一次操作后数列里的数都不为负 。** ### 输出格式 对于每一个操作 $4$ ,输出一行一个整数,表示答案 。题目描述
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.输入输出格式
输入格式
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.
输出格式
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