P7983 [JRKSJ R3] practiceZ


Qinqin gives you two sequences $a$ and $b$ of length $n$. You need to support a total of $m$ operations of three types: 1. `1 l r x`: Set all numbers in the interval $[l,r]$ of sequence $a$ to $x$. 2. `2 l r y`: Set all numbers in the interval $[l,r]$ of sequence $b$ to $y$. 3. `3 l r`: Compute $\sum_{i=l}^r \sum_{j=1}^{b_i} a_j$. The answer is taken modulo $2^{32}$.

All inputs are integers. Line $1$ contains two numbers $n,m$.\ Line $2$ contains $n$ numbers representing sequence $a$.\ Line $3$ contains $n$ numbers representing sequence $b$.\ The next $m$ lines each contain one operation. The format is the same as in the problem description.

For each operation of type $3$, output one integer per line as the answer.

**This problem uses bundled judging.** Note: The original time limit was 5 s. Since it was rather strict on constant factors, it was changed by the admins to 7 s. | $\text{Subtask}$ | $n\le$ | $m\le$ | Special property | Score | Dependencies | Time limit | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $500$ | $10^3$ | None | $10$ | None | $2\text{s}$ | | $2$ | $10^4$ | $10^4$ | None | $10$ | $1$ | $2\text{s}$ | | $3$ | $10^5$ | $10^5$ | None | $30$ | $1,2$ | $4\text{s}$ | | $4$ | $5\times 10^5$ | $3\times 10^5$ | Random testdata | $20$ | None | $5\text{s}$ | | $5$ | $5\times 10^5$ | $3\times 10^5$ | None | $30$ | $1,2,3,4$ | $5\text{s}$ | For $100\%$ of the data, $1\le n\le 5\times 10^5$, $1\le m\le 3\times 10^5$, $1\le a_i,x\le 10^9$, $1\le b_i,y\le n$. Translated by ChatGPT 5