You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

题目描述

给定一个长为 $n$ 的序列 $a$ ，每个位置有一种颜色，有 $m$ 次操作，支持：

1 l r x：区间 $[l,r]$ 的数都变成 $x$。

2 l r：查询有多少二元组 $(i,j)$ 满足 $l \leq i < j \leq r$ ，且 $a_i = a_j$。

本题强制在线，每次的 $l,r,x$ 需要 $\operatorname{xor}$ 上（上次答案 $\bmod 2^{32}$），也就是说使用 unsigned int 数据类型存储上次的答案即可，如果之前没有询问，则上次答案为 $0$。这里输出的答案不对 $\bmod 2^{32}$ 取模。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数表示序列 $a$。

之后 $m$ 行，每行形如 1 l r x 或 2 l r，表示上述的操作。

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案。

10 12
6 9 9 4 7 8 10 4 9 2
2 1 4
1 0 5 0
2 3 6
2 10 9
1 7 9 2
2 7 9
1 2 7 1
1 2 11 4
2 6 10
1 3 12 0
1 14 14 15
2 7 12

1
3
0
3
6
16

提示

Idea：nzhtl1477，Solution：nzhtl1477&ccz181078，Code：ccz181078，Data：nzhtl1477

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，没有修改操作。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，每次修改的区间长度不超过 $5$。

对于另外 $19\%$ 的数据，保证数据随机。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$，$1\leq a_{i},x\leq n$，$1\leq l\leq r\leq n$。