P5618 [SDOI2015] Road Construction

A certain country has $2N$ cities. These $2N$ cities form a $2$-row, $N$-column grid. The government now has a tourism development plan: it needs to choose two columns $L$ and $R$ $(L \leq R)$, and build some dedicated roads so that among all $2(R-L+1)$ cities between these two columns (including these two columns), every city can reach any other of these $2(R-L+1)$ cities using only the dedicated roads. A dedicated road can only be built between two cities in the same row and adjacent columns, or between the two cities in the same column, and building a road costs some amount. Since the government wants to reduce expenses as much as possible, after choosing $L$ and $R$, it will build only $2(R-L+1)-1$ dedicated roads, so that these roads form a tree structure. Now you need to help the government write a program to complete this task. Specifically, the task contains $M$ operations, each in one of the following formats: 1. `C x0 y0 x1 y1 w`: Because the situation between the city at row $x_0$, column $y_0$ and the city at row $x_1$, column $y_1$ has been re-evaluated, the cost to build a dedicated road between them becomes $w$. 2. `Q L R`: If the government chooses columns $L$ and $R$, ask for the minimum total expense.

The first line contains two integers $N$ and $M$. The second line contains $N-1$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $1$, column $i$ and the city at row $1$, column $i+1$. The third line contains $N-1$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $2$, column $i$ and the city at row $2$, column $i+1$. The fourth line contains $N$ integers. The $i$-th integer indicates the initial cost to build a dedicated road between the city at row $1$, column $i$ and the city at row $2$, column $i$. The next $M$ lines each contain one operation.

For each query operation, output one line containing the minimum expense you computed for the government.

For all testdata, $1 \leq N, M \leq 60000$, and at any time, the construction cost of any dedicated road does not exceed $10^4$. Translated by ChatGPT 5