P9711 [KMOI R1] Five Five Five Five (Hard)

“Things can be inferred from each other, and each has its place. So although branches split, they share the same trunk. This only reveals one end of it. Also, when analyzing principles through words and explaining structures with diagrams, it may be concise yet complete, clear yet not verbose. Readers will understand more than half just by thinking.” — Liu Hui.

Xiao Song has a sequence $A=\{a_1,a_2\dots,a_n\}$, where $\forall i\in [1,n],a_i\in[0,9]$. For $1\le l\le r\le n$, he defines $f(l,r)$ as the number of consecutive trailing $5$’s at the end of $\overline{a_la_{(l+1)}\dots a_r}$. For example, for the sequence $a=\{1,1,4,5,1,4\}$, $f(2,4)=1,f(1,3)=0$. Xiao Song will keep performing operations on this sequence. Specifically, he will do the following operations: - $(1,x,y)$: Change the $x$-th number to $y$ ($x\in[1,n],y\in[0,9]$). - $2$: Reverse the sequence $a$. For example, $\{1,1,4,5\}$ becomes $\{5,4,1,1\}$ after reversing. - $3$: Query the sequence. - $(4,l,r)$: Query the sequence. For each operation $3$, output: $$\Big(\sum\limits_{l=1}^ {n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$ For each operation $4$, output: $$\Big(\sum\limits_{i=l}^{r}a_i\Big) \bmod 10^9+7$$

The first line contains two positive integers $n,q$, representing the length of the sequence and the number of queries. The second line contains $n$ integers $a_1, a_2,\dots a_n$, representing the sequence $A$. The next $q$ lines each contain one or three positive integers, representing an operation.

For each operation $3$ and operation $4$, output the answer.

## Explanation for Sample $1$: | Operation | Sequence after the operation | Answer | | :----------: | :----------: | :----------: | | $(1,3,3)$ | $\{1,5,3\}$ | $/$ | | $3$ | $/$ | $2$ | | $(1,1,5)$ | $\{5,5,3\}$ | $/$ | | $(4,1,3)$ | $/$ | $13$ | ## Explanation for Sample $2$: | Operation | Sequence after the operation | Answer | | :----------: | :----------: | :----------: | | $3$ | $/$ | $4$ | | $2$ | $\{4,1,5,4,1,1\}$ | $/$ | | $3$ | $/$ | $3$ | | $(1,1,5)$ | $\{5,1,5,4,1,1\}$ | $/$ | |$(4,1,4)$|$/$|$15$| ## Constraints | Test Point ID | $n\le$ |$q\le$| Special Property | | :----------: | :----------: | :----------: | :----------: | |$1$|$100$|$100$|$/$| |$2,3$|$10^3$|$10^3$|$\mathbf{A}$| |$4$|$10^3$|$10^3$|$\mathbf{B}$| |$5\sim10$|$2\times 10^5$|$2\times 10^5$|$/$| |$11\sim13$|$2\times 10^5$|$2\times 10^5$|$\mathbf{A}$| |$14,15$|$2\times 10^5$|$2\times 10^5$|$/$| |$16\sim18$|$5\times 10^5$|$5\times 10^5$|$\mathbf{B}$| |$19\sim25$|$5\times 10^5$|$5\times 10^5$|$/$| Special property $\mathbf{A}$: There is no operation $2$. Special property $\mathbf{B}$: There is no operation $3$. For $100\%$ of the testdata: $1\le n\le 5\times 10^5$, $1\le q\le 5\times 10^5$. $\forall i\in [1,n]$, $a_i\in[0,9]$. Translated by ChatGPT 5