AGC016D XOR Replace（并查集）

AGC016D XOR Replace

一个序列，一次操作可以将某个位置变成整个序列的异或和。问最少几步到达目标序列。\(n \le 100000\)。

CODE

令最后一个数是初始异或和然后每次操作就是交换当前数和最后一个数。

忽略 \(a_i = b_i\) 的位置。

如果所有数互不相同，则答案很明显是 \(a_i\) 和 \(b_i\) 连边以后的边数 \(+\) 连通块个数。

否则会发现比如

0 2 2 3 3 (0)
2 0 3 2 3 (0)

这样的可以先用第一个环换出 \(2\) 来解决第二个环在换回去答案就是 \(4\)。所以把权值当做点，连边，答案就是边数 \(+\) 权值连通块个数（对于最后一个数要精细处理，是否 \(-1\) 取决于处理方式）。