P9057 [Ynoi2004] rpfrdtzls

Given $n, m, A$, maintain a sequence of sequences $a_1, \dots, a_n$. Initially, each $a_i$ contains one element $A + 1$. There are $m$ operations in total: - Modification: given $l, r, x$, for all $l \le i \le r$, insert the element $x$ to the front of sequence $a_i$. - Query: given $l, r$, query $\sum\limits_{i=l}^r F(a_i, A)$. Where $F((x_1, \dots, x_n), 0) = 0$. For $k > 0$, $F((x_1, \dots, x_n), k) = F((x_2, \dots, x_n), \lfloor \frac{k}{x_1} \rfloor) + 1$.

The first line contains three integers $n, m, A$. The next $m$ lines each describe an operation: $1, l, r, x$ denotes a modification operation, and $2, l, r$ denotes a query operation.

For each query operation, output one line containing the answer.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Constraints: for $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le A, x \le 10^9$, and $1 \le l \le r \le n$. For $25\%$ of the testdata, $n, m \le 100$. For $50\%$ of the testdata, $n, m \le 10^5$. For another $25\%$ of the testdata, $x \ne 1$. For the remaining $25\%$ of the testdata, there are no special restrictions. Translated by ChatGPT 5