测试数据来自 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\)。
• * l r x 小 G 对区间 \([l,r]\) 内的每个数乘 \(x\)。
• 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{mode(A,l,r)}\)。

输出格式

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

输入输出样例

输入样例 #1

输出样例 #1

数据范围及说明

数据范围

保证所有输入数据 \(n\le 10^5,m\le 10^4,a_i,x\le 10^{12},i\in [1,n]\)

测试点编号	\(n\le\)	\(m\le\)	\(a_{i},x\le\)	分值（共计）
\(1\sim20\)	\(100\)	\(10\)	\(10^3\)	\(20,1\hspace{0.5mm}\text{pts for each}\)
\(21\sim40\)	\(10^3\)	\(100\)	\(10^6\)	\(20,1\hspace{0.5mm}\text{pts for each}\)
\(41\sim60\)	\(10^4\)	\(100\)	\(10^9\)	\(20,1\hspace{0.5mm}\text{pts for each}\)
\(61\sim80\)	\(10^5\)	\(10^3\)	\(10^{10}\)	\(20,1\hspace{0.5mm}\text{pts for each}\)
\(81\sim100\)	\(10^5\)	\(10^4\)	\(10^{12}\)	\(20,1\hspace{0.5mm}\text{pts for each}\)

时空限制

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

出题团队

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

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

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

难度评估

• \(\hspace{1mm}\large{\text{ZZOI 基础}}\)
• \(\hspace{1mm}\large{\text{ZZOI 难度 5}}\)

数据说明

\(\normalsize{\text{The half of data were made by ZZA.}}\)
\(\normalsize{\text{The numbers of them are }}1\sim10,21\sim30,41\sim50,61\sim70,81\sim90.\)
\(\normalsize{\text{Of course,the others were made by GXZ.}}\)