测试数据来自 YujinSharp001/1012

P1004 小 G 的神人游戏 \(\text{I}\)

题目背景

小 Z 在机房突发奇想，邀请旁边的小 G 创作一个神人游戏给小小 L 玩耍，于是小 G 灵机一动，想出了一个区间上的游戏。由于小小 L 还在文化课的漩涡中，所以小 G 决定先让大 Z 玩耍。

题目描述

小 G 会给出一个整数序列 \(A[a_1,a_2,\dots,a_n]\)，并且会对这个序列进行一些修改操作并对大 Z 进行询问，每次询问当前区间的信息，要求大 Z 立刻作答，并强制在线。

输入格式

第一行输入两个正整数 \(n,m\)，表示输入序列长度和修改操作及询问的总次数。

第二行输入 \(n\) 个整数，表示序列 \(A[a_1,a_2,\dots,a_n]\)。

接下来 \(m\) 行，每行包含如下的修改操作或询问语句：

• + l r x 小 G 对区间 \([l,r]\) 内的每个数加 \(x\)，即 \(a_i=a_i+x\)，其中 \(i\in[l,r],x\in\mathbb{Z}\)。
• * l r x 小 G 对区间 \([l,r]\) 内的每个数乘 \(x\)，即 \(a_i=a_i\times x\)，其中 \(i\in[l,r],x\in\mathbb{Z}\)。
• ^ l r x 小 G 将区间 \([l,r]\) 内的每个数修改为其的 \(x\) 次幂，即 \(a_i=a_i^x\)，其中 \(i\in[l,r],x\in\mathbb{N}\)。
• 1 l r 小 G 向大 Z 询问区间 \([l,r]\) 内所有数的和，即 \(\sum \limits_{i=l}^{r}{a_i}\)。
• 2 l r 小 G 向大 Z 询问区间 \([l,r]\) 内所有数的最大值，即 \(\max(a_{l},a_{l+1},...,a_{r-1},a_{r})\)。
• 3 l r 小 G 向大 Z 询问区间 \([l,r]\) 内所有数的最大公约数，即 \(\gcd(a_l,a_{l+1},\dots,a_{r-1},a_r)\)。
• 4 l r 小 G 向大 Z 询问区间 \([l,r]\) 内没有出现过的最小自然数，即 \(\text{mex}(a_l,a_{l+1},\dots,a_{r-1},a_r)\)。
• 5 l r 小 G 向大 Z 询问区间 \([l,r]\) 内所有数的众数，即 \(\text{mode}(A,l,r)\)。

输出格式

对于每次询问，输出一个整数 \(ans\)，\(ans\) 的值为查询结果 \(res\) 与上次查询的答案 \(lastans\) 的异或和，即 \(ans=res \hspace{0.5mm} \operatorname{xor} \hspace{0.5mm} lastans\)，输出结果要对 \(998244353\) 取模。

输入输出样例

输入样例 #1

输出样例 #1

数据范围及说明

数据范围

保证所有输入数据 \(1\le n\le 10^5,1\le m\le 10^4,1\le l\le r\le n,|a_i|,|x|\le 10^{12}\)。

测试点编号	\(n\le\)	\(m\le\)	\(\lvert a_i \rvert,\lvert x \rvert\le\)	特殊性质
\(1\sim10\)	\(100\)	\(10\)	\(10^3\)	\(\text{ABC}\)
\(11\sim20\)	\(100\)	\(10\)	\(10^3\)	无
\(21\sim30\)	\(10^3\)	\(100\)	\(10^6\)	\(\text{BC}\)
\(31\sim40\)	\(10^3\)	\(100\)	\(10^6\)	无
\(41\sim50\)	\(10^4\)	\(100\)	\(10^9\)	\(\text{A}\)
\(51\sim60\)	\(10^4\)	\(100\)	\(10^9\)	无
\(61\sim70\)	\(10^5\)	\(10^3\)	\(10^{10}\)	\(\text{B}\)
\(71\sim80\)	\(10^5\)	\(10^3\)	\(10^{10}\)	无
\(81\sim90\)	\(10^5\)	\(10^4\)	\(10^{12}\)	\(\text{C}\)
\(91\sim100\)	\(10^5\)	\(10^4\)	\(10^{12}\)	无

特殊性质：

• 特殊性质 \(\text{A}\)：保证没有 ^（乘方求幂值）操作。
• 特殊性质 \(\text{B}\)：保证没有 4（\(\text{mex}\) 未出现过的最小自然数） 查询。
• 特殊性质 \(\text{C}\)：保证没有 5（\(\text{mode}\) 区间众数） 查询。

题目分值

测试点分值等分，共计 \(100\) 个测试点，总分 \(100\) 分，每个测试点 \(1\) 分。

\(100\hspace{0.5mm}\text{pts in total},1\hspace{0.5mm}\text{pts for each test point.}\)

时空限制

• 时间限制：1000 ms
• 空间限制：1024 MB

出题团队

\(\large{\text{ZZOI 神人出题组}}\)

\(\large{\text{ZZOI 河北正定中学信息学奥林匹克竞赛神人出题组}}\)

题目	出题	审题	数据	正解
\(Person\)	\(GXZ\)	\(ZZA\)	\(ZZA,GXZ\)	\(GXZ,ZZA\)

难度评估

• \(\hspace{1mm}\large{\text{ZZOI 基础} （\textcolor{blue}{Base}）}\)
• \(\hspace{1mm}\large{\text{ZZOI 难度 6} （水紫： \textcolor{purple}{省选/NOI-}）}\)

数据说明

\(\normalsize{\text{The half of data were made by ZZA.}}\)
\(\normalsize{\text{The numbers of them are }}1\sim5,11\sim15,21\sim25,31\sim35,41\sim45,51\sim55,61\sim65,71\sim75,81\sim85,91\sim95.\)
\(\normalsize{\text{Of course,the others were made by GXZ.}}\)

更新说明

1. 创建时间未知，2025 年。
2. 对题目进行了第一次大规模修改，删除了所有有关精度的问题，时间未知，2025 年。
3. 对题目进行了完善和修改，增添了 ^（乘方求幂值）操作、4（\(\text{mex}\) 未出现过的最小自然数） 查询，增添了特殊性质 \(\text{A,B,C}\)，时间于 2025.11.16 周日上午。