B 还是数据结构

时间限制: 1s
内存限制: 待定 MB

题目描述

对于非负整数 $x$，定义 $\text{p}(x)$ 为 $x$ 在二进制下的 $1$ 的个数，例如 $\text{p}(10)=p(1010_2)=2$。

对于非负整数 $x,y$，定义 $f(x,y)=\text{p}(x \oplus y)$，其中 $\oplus$ 是二进制异或。

对于长度为 $n$ 的非负整数序列 $b$ 和正整数 $k \ge 2$，我们定义它的价值如下：建立一个 $m$ 个点的无向图，点 $i$ 和 $j$ 之间有边当且仅当 $f(b_i,b_j) \ge k$。价值定义为图中大小为 $k$ 的简单环个数。特别地，若 $k=2$，价值为图中的边数。

给定非负整数序列 $a$，支持操作：

1. $1 \ l \ r \ x$ ：把 $a_l,a_{l+1},\dots,a_r$ 都异或 $x$。
2. $2 \ l \ r \ k$ ：查询序列 $a_l,a_{l+1},\dots,a_r$ 的价值，对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$。

后 $q$ 行每行四个整数表示操作。

输出格式

对于每个询问，输出一行一个非负整数表示答案，对 $998244353$ 取模。

输入输出样例

9 8
0 1 2 3 4 5 6 7 8
2 1 4 2
2 1 4 4
1 1 3 8
2 1 3 8
2 1 4 3
1 2 5 7
2 4 5 2
2 2 7 4

4
1
0
0
1
9

样例解释

第一次询问中，求序列 $[0,1,2,3]$ 在 $k=2$ 时的价值。图中有边 $(0,3)$，$(1,2)$，$(1,3)$，$(2,3)$，所以答案为 $4$。

第二次询问中，求序列 $[0,1,2,3]$ 在 $k=4$ 时的价值。图中恰有一个环 $(0,1,2,3)$，所以答案为 $1$。

第一次修改后，序列变成 $[8,9,10,3,4,5,6,7,8]$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 2*10^5$，$1 \le q \le 2*10^5$，$0 \le a_i < 2^{20}$，$0 \le x < 2^{20}$，$2 \le k \le n$。保证至少存在一次 $2$ 操作。

特殊性质 A：$n \le 100$，$q \le 100$。 特殊性质 B：不存在 $1$ 操作。 特殊性质 C：$1$ 操作中 $l=r$。 特殊性质 D：$2$ 操作中 $r-l+1 \leq 100$。