CF2042F Two Subarrays

You are given two integer arrays $ a $ and $ b $ , both of size $ n $ . Let's define the cost of the subarray $ [l, r] $ as $ a_l + a_{l + 1} + \cdots + a_{r - 1} + a_r + b_l + b_r $ . If $ l=r $ , then the cost of the subarray is $ a_l + 2 \cdot b_l $ . You have to perform queries of three types: - " $ 1 $ $ p $ $ x $ " — assign $ a_{p} := x $ ; - " $ 2 $ $ p $ $ x $ " — assign $ b_{p} := x $ ; - " $ 3 $ $ l $ $ r $ " — find two non-empty non-overlapping subarrays within the segment $ [l, r] $ with the maximum total cost and print their total cost.

The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ). The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ -10^9 \le b_i \le 10^9 $ ). The fourth line contains a single integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ). The next $ q $ lines contain the queries: one per line. Each query is of one of three types: - " $ 1 $ $ p $ $ x $ " ( $ 1 \le p \le n $ ; $ -10^9 \le x \le 10^9 $ ); - " $ 2 $ $ p $ $ x $ " ( $ 1 \le p \le n $ ; $ -10^9 \le x \le 10^9 $ ); - " $ 3 $ $ l $ $ r $ " ( $ 1 \le l < r \le n $ ). It is guaranteed that there is at least one query of the third type.

For each query of the third type, print the maximum possible total cost of two non-empty non-overlapping subarrays within the segment $ [l, r] $ .