Problem:


 MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem L: RMQ 2

Problem

長さ$N$の2つの数列$A$と$B$が与えられる。はじめ、数列$A$の$i$項目は$a_i$であり、数列$B$の$i$項目は$b_i$である。

以下のような形式の命令文が合計$Q$個与えられるので、与えられた順に処理を行うプログラムを作成せよ。

各命令文は3つの整数$x,y,z$で表される。

数列$A$の$y$項目の値を$z$にする。 ($x=1$のとき)

数列$B$の$y$項目の値を$z$にする。 ($x=2$のとき)

数列$A$の$y$項目から$z$項目の中で最小の値を見つけて報告する。 ($x=3$のとき)

数列$B$の$y$項目から$z$項目の中で最小の値を見つけて報告する。 ($x=4$のとき)

数列$A$を、数列$B$と全く同じになるように変更する。 ($x=5$のとき)

数列$B$を、数列$A$と全く同じになるように変更する。 ($x=6$のとき)

Input

入力は以下の形式で与えられる。

$N$

$a_{1}$ $a_{2}$ ... $a_{N}$

$b_{1}$ $b_{2}$ ... $b_{N}$

$Q$

$x_1$ $y_1$ $z_1$

$x_2$ $y_2$ $z_2$

...

$x_Q$ $y_Q$ $z_Q$

Constraints

入力は以下の条件を満たす。

  
$2 \le N \le 2 \times 10^5$

  
$2 \le Q \le 2 \times 10^5$

  
$1 \le a_i \le 10^9$

  
$1 \le b_i \le 10^9$

  
$1 \le x_i \le 6$

  
$1 \le y_i \le N $ ($1 \le x_i \le 4$のとき)

  
$y_i = -1$ ($x_i=5, 6$のとき)

  
$1 \le z_i \le 10^9$ ($x_i=1, 2$のとき)

  
$y_i \le z_i \le N$ ($x_i=3, 4$のとき)

  
$z_i = -1$ ($x_i=5, 6$のとき)

  
入力はすべて整数

Output

$x=3$または$x=4$の命令文が入力で与えられる度に、見つけた値を1行に出力する。
 

Sample Input 1

5
1 3 5 7 9
6 2 3 2 6
10
1 3 4
3 4 5
4 2 3
5 -1 -1
2 3 8
3 2 5
4 3 3
1 1 1
6 -1 -1
3 1 5

Sample Output 1

7
2
2
8
1



Sample input:
5
1 3 5 7 9
6 2 3 2 6
10
1 3 4
3 4 5
4 2 3
5 -1 -1
2 3 8
3 2 5
4 3 3
1 1 1
6 -1 -1
3 1 5


Sample output:
7
2
2
8
1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
    x, y, z = map(int, input().split())
    if x == 1:
        a[y] = z
    elif x == 2:
        b[y] = z
    elif x == 3:
        print(min(a[y:z+1]))
    elif x == 4:
        print(min(b[y:z+1]))
    elif x == 5:
        a = b[:]
    else:
        b = a[:]

Submission status: Time Limit Exceeded

Solution code:
import copy

input()
a = list(map(int,input().split()))
b = list(map(int,input().split()))

q = int(input())

for _ in range(q):
    [x,y,z] = map(int,input().split())
    if   x == 1:
        a[y-1] = z
    elif x == 2:
        b[y-1] = z
    elif x == 3:
        print(min(a[y-1:z]))
    elif x == 4:
        print(min(b[y-1:z]))
    elif x == 5:
        a = copy.deepcopy(b)
    elif x == 6:
        b = copy.deepcopy(a)