测试数据来自 YujinSharp001/1012

P1004 小 G 的神人游戏

题目背景

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

题目描述

小 G 会给出一个正整数序列 \(A[a_1,a_2,\dots,a_n]\)，小 G 会进行一些修改操作并对大 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 k 小 G 向大 Z 询问第 \(k\) 次修改后区间 \([l,r]\) 内所有数的和，即 \(\sum \limits_{i=l}^{r}{a_i}\)。
• 2 l r k 小 G 向大 Z 询问第 \(k\) 次修改后区间 \([l,r]\) 内的最大值，即 \(max(a_{l},a_{l+1},...,a_{r-1},a_{r})\)。
• 3 l r k 小 G 向大 Z 询问第 \(k\) 次修改后区间 \([l,r]\) 内所有数的最大公约数，即 \(gcd(a_l,a_{l+1},\dots,a_{r-1},a_r)\)。
• 4 l r k 小 G 向大 Z 询问第 \(k\) 次修改后区间 \([l,r]\) 内所有数的众数。
• 5 l r k 小 G 向大 Z 询问第 \(k\) 次修改后区间 \([l,r]\) 内所有数的正弦值的和，即 \(\sum \limits_{i=l}^{r}\sin{a_i}\)

输出格式

对于每次询问，输出一个整数 \(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\le 10^{12},i\in [1,n]\)

测试点编号	\(n\le\)	\(m\le\)	\(a_{i},x\le\)
\(1,2\)	\(100\)	\(10\)	\(10^3\)
\(3,4\)	\(10^3\)	\(100\)	\(10^6\)
\(5,6\)	\(10^4\)	\(100\)	\(10^9\)
\(7,8\)	\(10^5\)	\(10^3\)	\(10^{10}\)
\(9,10\)	\(10^5\)	\(10^4\)	\(10^{12}\)

时空限制

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

出题团队

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