P6309 "Wdsr-1" Human Village

- This is the place in Gensokyo where the most humans live. Because there are many shops that even youkai visit, all kinds of youkai may come here. However, they are all well-behaved youkai, so this is a peaceful place. (×1 The Hieda family lives here, without doubt also in the Human Village.) - Daily necessities for humans can all be bought here. Some people who specialize in exterminating youkai also live here, so life here is relatively safe. - As for why the Human Village is not attacked, it is because the sages of youkai protect it behind the scenes. (×2 If the humans in Gensokyo were to go extinct, the youkai would not have it easy either.) If you do not go out, you will not run into great trouble. - If you meet a youkai stronger than yourself while going out (×3 There is a high probability that the other side is stronger than you.), greet them respectfully. Also, surprisingly, many shops stay open until late at night, and at night they become youkai-only shops. Youkai are mostly active at night, and shops also thrive during that time. It can be said that youkai are actually very good customers. - Especially in sake shops, humans and youkai having fun together has become an everyday sight. $$\tag*{——Excerpt from "Touhou Suzunaan: Perfect Memento in Strict Sense"}$$

Although the Human Village can be said to be the safest place for humans in all of Gensokyo, accidents may still happen when an incident occurs, so shelters need to be built. The Human Village can be abstracted as a coordinate axis, on which there are $n$ points with houses built. The coordinates of these houses are $x_1, x_2, ..., x_n$, and in the $i$-th house there live $v_i$ residents. Each time an incident occurs, a **coordinate-contiguous** segment of houses will be affected, and then it is necessary to build a shelter at some coordinate. The "inconvenience" of a shelter is the sum, over **every resident** in the affected houses, of their distance to the shelter. (For example, suppose only house $i$ is affected. Then the "inconvenience" of building the shelter at $z$ is $v_i*|x_i-z|$.) Of course, the Human Village in Gensokyo cannot stay unchanged, so both house positions and resident counts may change. Specifically, you need to process $m$ queries or modifications. Each input is in one of the following formats: - `1 l r`: Query, when the houses whose **coordinates** lie in $[l, r]$ are affected by the incident, among all ways to build a shelter, what is the minimum possible "inconvenience". - `2 a b c`: Modify the $a$-th house: change its coordinate to $b$, and change the number of residents living in it to $c$. **Notes:** - In operation `1`, the "affected by the incident" is only a hypothesis, so it does not affect later queries. - In operation `2`, the changed object is the $a$-th house, not the house whose coordinate is $a$.

The first line contains two integers, $n, m$. The second line contains $n$ integers, $x_i$. The third line contains $n$ integers, $v_i$. The next $m$ lines each describe one operation.

For each `1 l r` operation, output the minimum "inconvenience" for building the shelter.

**[Sample Explanation]** For the first query, there are two houses affected: one at $x=4$ with $3$ residents, and one at $x=7$ with $6$ residents. When the shelter is built at $x=7$, the "inconvenience" is: $$\left\vert 7 - 4 \right\vert \times 3 + \left\vert 7 - 7 \right\vert \times 6 = 9$$ It can be proven that $9$ is the minimum "inconvenience" among all ways to build a shelter. -------------------- **[Constraints]** - For $100\%$ of the data: $1 \le n, m \le 3 \times 10 ^ 5$. $1 \le a \le n$, $-10 ^ 9 \le l \le r \le 10 ^ 9$, $-10 ^ 9 \le x_i, b \le 10 ^ 9$, $0 \le v_i, c \le 10 ^ 3$. - **Detailed constraints:** Let $mx$ be the maximum absolute value among all input integers. Test point ID | $n, m \le$ | $mx \le$ | Score :-: | :-: | :-: | :-: $1$ | $100$ | $100$ | $10$ $2$ | $8 \times 10 ^ 3$ | $8 \times 10 ^ 3$ | $15$ $3$ | $8 \times 10 ^ 3$ | $10 ^ 9$ | $5$ $4$ | $10 ^ 5$ | $10 ^ 5$ | $30$ $5$ | $10 ^ 5$ | $10 ^ 9$ | $10$ $6$ | $3 \times 10 ^ 5$ | $10 ^ 9$ | $30$ Translated by ChatGPT 5