{"problem":{"name":"[KMOI R1] 五五五五（Hard）","description":{"content":"小宋有一个序列 $A=\\{a_1,a_2\\dots,a_n\\}$，其中 $\\forall i\\in [1,n],a_i\\in[0,9]$。 对于 $1\\le l\\le r\\le n$，他记 $f(l,r)$ 等于 $\\overline{a_la_{(l+1)}\\dots a_r}$ 的末尾连续 $5$ 的个数。 例如：对于序列 $a=\\{1,1,4,5,1,4\\}$，$f(2,4)=1,f(1","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9711"},"statements":[{"statement_type":"Markdown","content":"小宋有一个序列 $A=\\{a_1,a_2\\dots,a_n\\}$，其中 $\\forall i\\in [1,n],a_i\\in[0,9]$。\n\n对于 $1\\le l\\le r\\le n$，他记 $f(l,r)$ 等于 $\\overline{a_la_{(l+1)}\\dots a_r}$ 的末尾连续 $5$ 的个数。\n\n例如：对于序列 $a=\\{1,1,4,5,1,4\\}$，$f(2,4)=1,f(1,3)=0$。\n\n不过小宋会对这个序列不断地操作，具体地，他会做以下操作：\n\n- $(1,x,y)$：将第 $x$ 个数改为 $y$（$x\\in[1,n],y\\in[0,9]$）。\n\n- $2$: 将序列 $a$ 反转，例如 $\\{1,1,4,5\\}$ 反转之后就是 $\\{5,4,1,1\\}$。\n\n- $3$：对序列进行询问。\n\n- $(4,l,r)$：对序列进行询问。\n\n对于每一种操作 $3$，请你输出:\n\n$$\\Big(\\sum\\limits_{l=1}^\n{n}\\sum\\limits_{r=l}^{n} f(l,r)\\Big) \\bmod 10^9+7$$\n\n对于每一个操作 $4$，请你输出：\n\n$$\\Big(\\sum\\limits_{i=l}^{r}a_i\\Big) \\bmod 10^9+7$$\n\n## Input\n\n第一行两个正整数 $n,q$，表示序列的数个数和询问的个数。\n\n第二行 $n$ 个整数 $a_1, a_2,\\dots a_n$，表示序列 $A$。\n\n接下来 $q$ 行，每行一个或三个正整数，表示一次操作。\n\n## Output\n\n对于每一次操作 $3$ 和操作 $4$，输出答案。\n\n[samples]\n\n## Background\n\n“事类相推，各有攸归，故枝条虽分而同本干知，发其一端而已。又所析理以辞，解体用图，庶亦约而能周，通而不黩，览之者思过半矣。”——刘徽\n\n## Note\n\n## 样例 $1$ 解释：\n\n| 操作 | 操作后的序列 | 答案 |\n| :----------: | :----------: | :----------: |\n| $(1,3,3)$ | $\\{1,5,3\\}$ | $/$ |\n| $3$ | $/$ | $2$ |\n| $(1,1,5)$ | $\\{5,5,3\\}$ | $/$ |\n| $(4,1,3)$ | $/$ | $13$ |\n\n## 样例 $2$ 解释：\n\n| 操作 | 操作后的序列 | 答案 |\n| :----------: | :----------: | :----------: |\n| $3$ | $/$ | $4$ |\n| $2$ | $\\{4,1,5,4,1,1\\}$ | $/$ |\n| $3$ | $/$ | $3$ |\n| $(1,1,5)$ | $\\{5,1,5,4,1,1\\}$ | $/$ |\n|$(4,1,4)$|$/$|$15$|\n## 数据范围\n| 测试点编号 | $n\\le$ |$q\\le$| 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |\n|$1$|$100$|$100$|$/$|\n|$2,3$|$10^3$|$10^3$|$\\mathbf{A}$|\n|$4$|$10^3$|$10^3$|$\\mathbf{B}$|\n|$5\\sim10$|$2\\times 10^5$|$2\\times 10^5$|$/$|\n|$11\\sim13$|$2\\times 10^5$|$2\\times 10^5$|$\\mathbf{A}$|\n|$14,15$|$2\\times 10^5$|$2\\times 10^5$|$/$|\n|$16\\sim18$|$5\\times 10^5$|$5\\times 10^5$|$\\mathbf{B}$|\n|$19\\sim25$|$5\\times 10^5$|$5\\times 10^5$|$/$|\n\n特殊性质 $\\mathbf{A}:$ 没有操作 $2$。\n\n特殊性质 $\\mathbf{B}:$ 没有操作 $3$。\n\n对于 $100\\%$ 的数据：$1\\le n\\le 5\\times 10^5$，$1\\le q\\le 5\\times 10^5$。\n\n $\\forall i\\in [1,n]$，满足 $a_i\\in[0,9]$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9711","tags":["线段树","平衡树","树状数组","O2优化"],"sample_group":[["3 4\n1 5 5\n1 3 3\n3\n1 1 5\n4 1 3","2\n13"],["6 5\n1 1 4 5 1 4\n3\n2\n3\n1 1 5\n4 1 4","4\n3\n15"]],"created_at":"2026-03-03 11:09:25"}}