Two Subarrays
Contest: Educational Codeforces Round 172 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, dp, implementation, matrices

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.

Input format:
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.

Output format:
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]$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
7
3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1
6
3 1 7
1 2 0
3 3 6
2 5 -3
1 3 2
3 1 5

Example output:
18
7
16

Example input:
10
2 -1 -3 -2 0 4 5 6 2 5
2 -4 -5 -1 6 2 5 -6 4 2
10
3 6 7
1 10 -2
3 5 7
3 2 8
2 1 -5
2 7 4
3 1 3
3 3 8
3 2 3
1 4 4

Example output:
23
28
28
-17
27
-22

Editorial:
To begin with, let's understand how to calculate the answer if we consider only one query of the third type. For this, we can use the following dynamic programming: $$$dp_{i, k}$$$ — the maximum result if we have considered the first $$$i$$$ elements and chosen $$$k$$$ boundaries of subsegments (i.e., $$$k=0$$$ — the first segment has not started yet, $$$k=1$$$ — the first segment has started, $$$k=2$$$ — the first segment is finished, but the second segment hasn't started yet, and so on). The transitions in this dynamic programming are quite straightforward: we can select the current element as the next boundary of the subsegment (increase $$$k$$$ by $$$1$$$), in which case we have to increase the value of dynamic programming by $$$b_{l+i}$$$; or we can keep the current value of $$$k$$$. Additionally, the dynamic programming value needs to be increased by $$$a_{l+i}$$$ if the value of $$$k$$$ corresponds to an open segment ($$$k=1$$$ or $$$k=3$$$). Note that an element can be both the left and the right border of the segment at the same time; so we also need a transition from $$$k=0$$$ to $$$k=2$$$ and from $$$k=2$$$ to $$$k=4$$$.
Note that the transition from $$$dp_{i}$$$ to $$$dp_{i + 1}$$$ requires only $$$7$$$ numbers: $$$a_i$$$, $$$b_i$$$, $$$dp_{i, 0}, dp_{i, 1}, \dots, dp_{i, 4}$$$. Therefore, this dynamic programming can be easily packaged within some data structure, for example, a segment tree.
In each vertex of the segment tree, let's store a transition matrix $$$mat_{i, j}$$$ of size $$$5 \times 5$$$ — the maximum result if we started in this segment in state with $$$k = i$$$ and must end in state with $$$k =j$$$. This matrix is easy to update when changing values in the arrays $$$a$$$ and $$$b$$$, and it is also easy to merge (to merge two such matrices, it is necessary to consider triples of the form $$$0 \le i \le j \le k \le 4$$$, and there are only $$$35$$$ of them).
Thus, we know how to perform one query in $$$O(35\log{n})$$$.
Note that you should keep a static size array in each vertex of the segment tree (for example, you can use std::array) in C++; if you use something like a std::vector, it will consume much more memory (static arrays require about $$$200$$$ bytes for each vertex of the segment tree, which is already a lot). This also works faster in practice, even though the asymptotic complexity of the solution is the same.