P11071 「QMSOI R1」 Distorted Fate
题目背景
**O Fortuna velut luna statu variabilis……**
（图片来自 Phigros 曲绘，侵删。）
加强版 [T512613](https://www.luogu.com.cn/problem/T512613)。
题目描述
Geopelia 需要捕捉到一种特殊的，不同于黑洞的引力波。
第 $i$ 个引力波有着一个频率 $A_i$，而多个引力波会互相影响，叠加，形成一个频率更快的引力波。
具体的，对于一个长度为 $n$ 的序列 $A$，$A$ 中所有引力波叠加起来的频率 $f(A)$ 为：$\bigcup\limits_{i=1}^n A_i$。其中 $\bigcup$ 表示按位或。
现在，Geopelia 需要知道几段以同一引力波开始的区间的频率之和。
也就是说，Geopelia 要向你询问：
$$
\sum_{i=l}^rf(A[l,i])
$$
的值，其中 $A[l,r]$ 为 $A_l,A_{l+1},\cdots,A_{r-1},A_r$ 组成的序列。
但不幸的是，由于幽蓝边界的引力影响，某一个区间 $[l,r]$ 中所有引力波的频率可能会异或上一个值 $x$。
Geopelia 想实时更新她的数据，你可以帮帮她吗？
她知道引力波的频率可能很高，所以你只需要告诉她答案 $\bmod \ 2^{30}$ 的值就可以了。
## 形式化题意
给定一个长度为 $n$ 的数组 $A$，你需要完成以下 $q$ 次操作。
1. ```1 l r x``` 将 $A_i(l\le i\le r)$ 异或上 $x$。
2. ```2 l r``` 求：
$$
(\sum_{i=l}^r\bigcup_{j=l}^i A_j) \bmod 2^{30}
$$
其中 $\bigcup$ 表示按位或。
输入格式
无
输出格式
无
说明/提示
### 样例解释
对于第一组询问：此时 $A=\{1,2,3\}$，所以答案为 $1+1\cup 2+1\cup 2\cup 3=1+3+3=7$。
对于第二组询问：此时 $A=\{3,0,3\}$，所以答案为 $3+3\cup 0+3\cup 0\cup 3=3+3+3=9$。
### 数据范围
**本题使用 subtask 进行捆绑测试**，每个 subtask 的具体分值如下：
| 子任务 | $n$ | $q$ | 时间 | 空间 | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: |:----------:|
| $0$ | $\le 100$ | $\le 100$ | $1s$ | $512MB$ | $20$ |
| $1$ | $\le 2\times 10^4$ | $\le 2\times 10^4$ | $1s$ | $512MB$ |$20$ |
| $2$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $512MB$ |$20$ |
| $3$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $\color{red}100MB$ |$40$ |
对于所有数据，满足 $0\le a_i,x< 2^{30}$，$1\le l\le r\le n$。
```
INITALIZING……
SCANING……
CONNECTING……__PhigrOS Client Login
TIME_OUT!
CONNECTING……__Unknown
SUCCESS!
————————
……九……鸟……
……鸠……！
……喂？
…听得到吗？
鸠?![SIGNAL LOST]
```