문제
위 그림처럼 N 잔의 콜라들과 N 개의 피자 조각들이 일렬로 나열되어 있다.
각 콜라들과 피자 조각들은 맛의 정도가 다 다른데, 이는 정수로 주어진다.
정올이는 이 중 1 잔의 콜라와, 1 개의 피자 조각을 선택하여 먹는다.
항상 콜라는 왼손으로, 피자는 오른손으로 먹기에,
선택된 피자 조각의 위치는 선택된 콜라의 위치보다 오른쪽에 있어야 한다. ( 인덱스가 더 커야 한다. )
이 조건을 만족하면서 콜라와 피자 조각을 골랐을 때, 둘의 맛의 합이 최대가 되도록 하고 싶다.
Q 개의 명령이 들어오는데, 세 가지 형태 중 하나로 들어온다.
i 번째 콜라의 맛을 x 로 바꾼다.
i 번째 피자 조각의 맛을 x 로 바꾼다.
두 수 L, R ( 1 ≤ L < R ≤ N ) 에 대하여, L번째 ~ R번째 칸 범위에서만 콜라와 피자 조각을 고를 수 있을 때, 맛의 합의 최대를 출력한다.
입력
첫 줄에 N 이 입력된다. ( 1 ≤ N ≤ 100,000 )
두 번째 줄에, 일렬로 콜라들의 맛이 N 개의 정수로 입력된다. ( 100만 이하의 자연수 )
세 번째 줄에, 일렬로 피자 조각들의 맛이 N 개의 정수로 입력된다. ( 100만 이하의 자연수 )
네 번째 줄에 쿼리의 수 Q 가 입력된다. ( 1 ≤ Q ≤ 100,000 )
세 가지 형태의 명령들이 입력된다.
1 i x : i 번째 콜라의 맛을 x 로 바꾸는 명령 ( 1 ≤ i ≤ N, x 는 100만 이하의 자연수 )
2 i x : i 번째 피자 조각의 맛을 x 로 바꾸는 명령 ( 1 ≤ i ≤ N, x 는 100만 이하의 자연수 )
3 L R : L번째 ~ R번째 칸 범위에서만 콜라와 피자 조각을 고를 수 있을 때, 맛의 합의 최대를 출력하는 명령
출력
3번 명령이 들어올 때마다 적절한 답을 출력하자. 무조건 3번 명령은 1번 이상 주어진다.
예제
10
6 2 1 2 7 5 9 4 7 5
2 3 4 9 7 8 4 5 9 6
6
3 3 8
1 5 1
3 3 8
3 7 9
2 9 6
3 3 8
15
14
18
14
로그인해야 코드를 작성할 수 있어요.