{"problem":{"name":"『STA - R1』好吃的智慧果子","description":{"content":"**形式化题面** 维护一个序列 $\\{a_n\\}$，每次操作给五个非负整数 $l, r, k, p, c$，对于所有 $i\\in[l,r]$，将 $a_i\\gets (f_{a_i}^k+c)\\bmod p$。 其中 $f$ 是 Fibonacci 数列，定义为： $$f_n=\\begin{cases}n&n\\leqslant 1\\\\f_{n-1}+f_{n-2}&n>1\\end{cases","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":512000},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8878"},"statements":[{"statement_type":"Markdown","content":"**形式化题面**\n\n维护一个序列 $\\{a_n\\}$，每次操作给五个非负整数 $l, r, k, p, c$，对于所有 $i\\in[l,r]$，将 $a_i\\gets (f_{a_i}^k+c)\\bmod p$。\n\n其中 $f$ 是 Fibonacci 数列，定义为：\n$$f_n=\\begin{cases}n&n\\leqslant 1\\\\f_{n-1}+f_{n-2}&n>1\\end{cases}$$\n***\n\n**原题面**\n\n~~神机妙算的~~ $\\mathfrak{Morlin}$ 早就知道 $\\mathfrak{char\\_phi}$ 很聪明，所以他会不定时改密码。\n\n每个密码箱上有一个数字，组成了数列 $\\{a_n\\}$。\n\n关于密码有 $m$ 次操作，每次操作给定五个整数 $l, r, k, p, c$，表示将满足 $l \\leqslant i \\leqslant r$ 将 $a_i$ 变成 $(f_{a_i}^k+c) \\bmod p$（$f_i$ 代表斐波那契数列的第 $i$ 项；保证 $l \\leqslant r$）。\n\n$\\mathfrak{char\\_phi}$ 搞了一个记录器记录下了 $\\mathfrak{Morlin}$ 的操作。现在，他把记录器给了你，希望你能在 $\\mathfrak{Morlin}$ 操作完后搞出所有密码箱的密码。\n\n## Input\n\n第一行，两个整数 $n, m$，表示果子的数量和操作次数。\n\n第二行，$n$ 个整数为数列 $a$，表示每个密码箱上的数字。\n\n接下来 $m$ 行，表示 $\\mathfrak{Morlin}$ 的操作 $l, r, k, p, c$。\n\n## Output\n\n一行，表示所有密码箱的密码，每个密码间使用空格隔开。\n\n[samples]\n\n## Background\n\n在上古时代，$-(2077^{-1}\\ \\ (mod=2035))$ 年，$\\mathfrak{Morlin}$ 种下了一棵非常珍贵的$\\colorbox{black}{\\textcolor{red}{\\textbf{智♂慧♂树♂}}}$，被 $\\mathfrak{char\\_phi}$ 看见了。\n\n过了 $114810$ 年，树上结出了 $\\colorbox{black}{\\textcolor{blue}{\\textbf{智♂慧♂果♂子♂}}}$。  \n又过了 $1919514$ 年，果子成熟了，$\\mathfrak{char\\_phi}$ 非常馋。\n\n$\\mathfrak{char\\_phi}$ 十分想吃果子，但是~~神机妙算的~~ $\\mathfrak{Morlin}$ 早就知道 $\\mathfrak{char\\_phi}$ 想要吃他的果子，所以把每个果子都装进了密码箱。\n\n现在，$\\mathfrak{char\\_phi}$ 把偷果子这项重任托付给了你。  \n\n## Note\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| Subtask | $\\bm{n,m\\leqslant}$ | 分值 | 特殊性质 |\n| :--: | :--: | :--: | :--: |\n| $1$ | $10^3$ | $10$ | 无 |\n| $2$ | $10^5$ | $10$ | $p \\leqslant 2$ |\n| $3$ | $10^5$ | $20$ | $p \\leqslant 3$ |\n| $4$ | $10^5$ | $60$ | 无 |\n\n对于 $100\\%$ 的数据，$1 \\leqslant n, m \\leqslant 10^5$，$1 \\leqslant a_i, p, k \\leqslant 100$，$0 \\leqslant c \\leqslant 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8878","tags":["线段树","O2优化","置换"],"sample_group":[["6 2\n1 1 4 5 1 4\n2 4 2 100 3\n3 5 1 97 5","1 4 52 44 6 4"]],"created_at":"2026-03-03 11:09:25"}}