【MX-X2-T5】「Cfz Round 4」Xor-Forces
题目背景
原题链接:<https://oier.team/problems/X2E>。
---
✿(。◕ᴗ◕。)✿
题目描述
给定一个长度为 $n=2^k$ 的数组 $a$,下标从 $0$ 开始,维护 $m$ 次操作:
1. 操作一:给定 $x$,设数列 $a'$ 满足 $a'_i=a_{i\oplus x}$,将 $a$ 修改为 $a'$。其中 $\oplus$ 表示按位异或运算。
2. 操作二:给定 $l,r$,查询 $a$ 的下标在 $l,r$ 之间的子数组有多少颜色段。**不保证 $\bm {l\le r}$,若 $\bm{l > r}$,请自行交换 $\bm{l,r}$。**
其中,一个极长的所有数都相等的子数组称为一个颜色段。
部分测试点要求强制在线。
输入输出格式
输入格式
第一行三个整数 $T,k,m$,其中 $T \in \{ 0, 1 \}$ 为决定是否强制在线的参数。
第二行 $n$ 个整数 $a_0, \ldots, a_{n-1}$。
接下来 $m$ 行,每行两或三个整数,描述一次操作。第一个整数 $\mathit{op}$ 表示操作类型。
- 若 $op=1$,为操作一,接下来一个整数 $x'$,满足 $x=x'\oplus(T\times \mathit{lst})$。
- 若 $op=2$,为操作二,接下来两个整数 $l',r'$,满足 $l=l'\oplus(T\times \mathit{lst})$,$r=r'\oplus(T\times \mathit{lst})$。**不保证 $\bm{l \le r}$,若 $\bm{l > r}$,请自行交换 $\bm{l, r}$。**
- 其中 $\mathit{lst}$ 表示上次询问的答案。特别地,如果此前没有询问操作,则 $\mathit{lst}=0$。
输出格式
输出若干行,每行包含一个整数,依次表示每个询问的答案。
输入输出样例
输入样例 #1
0 3 3
1 2 1 3 2 4 5 1
2 1 5
1 3
2 5 1
输出样例 #1
5
4
输入样例 #2
1 3 3
1 2 1 3 2 4 5 1
2 1 5
1 6
2 0 4
输出样例 #2
5
4
输入样例 #3
1 4 16
12 9 5 9 12 12 9 12 9 16 5 9 12 16 9 5
2 0 4
1 15
2 14 0
1 15
2 6 0
2 4 14
1 0
1 14
2 4 10
2 6 3
1 7
2 4 13
1 3
1 3
2 4 3
2 15 2
输出样例 #3
5
7
4
7
9
5
7
2
11
说明
**【样例解释 #1】**
此样例允许离线。
初始时 $a=[1,2,1,3,2,4,5,1]$。
$a$ 的下标在 $1,5$ 之间的子数组为 $[2,1,3,2,4]$,它的颜色段数为 $5$。
进行重排操作后,$a=[3,1,2,1,1,5,4,2]$。
$a$ 的下标在 $5,1$ 之间的子数组为 $[1,2,1,1,5]$,它的颜色段数为 $4$。
**【样例解释 #2】**
此样例除强制在线外,与样例 \#1 完全一致。
**【数据范围】**
对于所有测试数据,$T \in \{ 0, 1 \}$,$0\le k\le 18$,$n=2^k$,$1\le m\le 2\times 10^5$,$1\le a_i\le n$,$\mathit{op} \in \{ 1, 2 \}$,$0\le x,l,r < n$。
**本题采用捆绑测试。**
- Subtask 1(15 points):$T=1$,$k\le 10$,$m\le 10^3$。
- Subtask 2(15 points):$T=1$,不存在操作一。
- Subtask 3(20 points):$T=1$,对于所有操作二,要么 $l=0,r=n-1$,要么 $l=n-1,r=0$。
- Subtask 4(20 points):$T=0$。
- Subtask 5(30 points):$T=1$。
**注意:Subtask 5 依赖前四个 Subtask,只有通过前四个 Subtask 才能尝试获得该 Subtask 的分数。**