P7131 "RdOI R1" Transformation (turn)

There are $n$ transformations. The $i$-th transformation has two attributes $p_i$ and $q_i$. When this transformation is applied to $x$, $x$ becomes $f_i(x)$. The definition of $f_i(x)$ is: $$f_i(x)=\left\lfloor\dfrac{x}{p_i}\right\rfloor+q_i$$ You are given $m$ operations. There are two types of operations: A **modify** operation can change the attribute values of a transformation. A **query** operation gives $x$ and two indices $s$ and $t$. You need to compute and output: $$f_{t}(f_{t-1}(\cdots f_{s+1}(f_{s}(x))))$$

The first line contains two positive integers $n$ and $m$. The second line contains $n$ integers, representing $p_1,p_2,\cdots,p_n$. The third line contains $n$ integers, representing $q_1,q_2,\cdots,q_n$. The next $m$ lines each describe one operation: A modify operation starts with the letter `m`, followed by three parameters $i,p',q'$, meaning to modify the $i$-th transformation’s attributes to $p',q'$. It is guaranteed that at any time the attributes satisfy $1\leq p_i\leq 1000, 0\leq q_i\leq 1000$. A query operation starts with the letter `q`, followed by three parameters $x,s,t$. The meaning is as described above. It is guaranteed that $s\leq t, 0\leq x\leq 10^6$.

For each query operation, output one integer, the required answer, separated by newlines.

Constraints - For $20\%$ of the testdata, $1 \le n \le 10^3,1 \le m \le 10^4$. - For another $30\%$ of the testdata, $1 \le n \le 10^4,1 \le m \le 10^5$. - For $100\%$ of the testdata, $1 \le n \le 10^5,1 \le m \le 2 \times 10^5$. --- File Input/Output **(for simulation; not needed when submitting code)** - Filename: `turn.cpp` - Input filename: `turn.in` - Output filename: `turn.out` Translated by ChatGPT 5