问题 J: 二进制与、平方和

问题 J: 二进制与、平方和

时间限制: 3 Sec  内存限制: 512 MB
提交: 111  解决: 25
[状态] [讨论版] [提交] [命题人:]
题目描述
请你维护一个长度为 n 的非负整数序列 a1,a2,…,an,支持以下两种操作:
  1. 第一种操作会将序列 al,al+1,…,a中的每个元素,修改为各自和 x 的"二进制与"(Bitwise binary AND)的值,其中 l,r,x 在每次操作时会给定;
  2. 第二种操作会询问序列 al,al+1,…,ar 中所有元素的平方和模 998244353的值,即 ∑i=lrai2 模 998244353,其中 l,r在每次操作时会给定。
总共有 q 次操作,请你在维护序列的过程中,输出第二种操作所询问的答案。注意需要取模。
输入
第一行,一个整数 n (1≤n≤3×105),表示序列的长度。
第二行,共 n 个整数 ai (0≤ai<224),表示序列。
第三行,一个整数 q (1≤q≤3×105),表示询问的数量。
接下来 q 行,每行表示一个操作,输入有两种格式:
  1. 第一种操作的格式为 "1 l r x",表示将序列中编号在区间  [l,r]  的所有元素,修改为和 x 二进制与操作后的值,其中  1≤l≤r≤n0≤x<224
  2. 第二种操作的格式为 "2 l r",表示询问序列中编号在区间  [l,r]  的所有元素的平方和,模  998244353 的值,其中  1≤l≤r≤n。
数据保证至少有一个第二种操作,即保证至少询问一次答案。
输出
每当遇到第二种操作时,输出询问的答案。注意需要取模。
样例输入 Copy
3
13 31 28
4
2 1 3
1 3 3 25
1 1 2 18
2 2 3
样例输出 Copy
1914
900
提示
样例输入二
5
9 11 12 5 1
7
2 1 3
1 3 3 0
1 1 3 9
1 4 5 13
2 1 3
1 4 5 14
2 1 5


样例输出二
346
162
178


样例输入三
4
16777215 16777215 16777215 16777214
4
2 2 2
1 1 4 16777214
2 1 4
2 3 4


样例输出三
981185168
795789897
897017125


"二进制与"(Bitwise binary AND)结果的第 i 个二进制位为 1,当且仅当两个操作数的第 i 位都为 1。