33OJ
登录 注册

#P17625. [qaswed12 OI R1] Xor Xor Mex

    ID: 20214 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>O2优化吉司机线段树 segment tree beats

[qaswed12 OI R1] Xor Xor Mex

背景

还有第三关?

题目描述

Gcend 在配置 T4 的数据时,发现自己根本不会写 checker.cpp!所以他需要你帮忙实现 checker.cpp。

qaswed12 给出了一个长度为 nn 的整数序列 aa,你需要求出:

$$\bigoplus\limits_{l=1}^{n}\bigoplus\limits_{r=l}^{n}\operatorname{mex}(l,r)$$

其中 mex⁡(l,r)\operatorname{mex}(l,r) 定义为在 al,al+1,...,ara_l,a_{l+1},...,a_r 中未出现的最小非负整数。

⨁\bigoplus 符号与 ∑\sum 符号的定义类似,求和变为求异或和,以及 ⊕\oplus 符号表示两数按位异或。

输入格式

第一行,一个整数 nn,表示数组的长度。

第二行,一共 nn 个整数,表示 aia_i。

输出格式

一行,一个整数,表示答案。

3
1 0 1
3

提示

样例解释 #1

$\begin{aligned} & \bigoplus\limits_{l=1}^{3}\bigoplus\limits_{r=l}^{3}\operatorname{mex}(l,r) \\ = & \operatorname{mex}(1,1) \oplus \operatorname{mex}(1,2) \oplus \operatorname{mex}(1,3) \oplus \operatorname{mex}(2,2) \oplus \operatorname{mex}(2,3) \oplus \operatorname{mex}(3,3) \\ = & \,0 \oplus 2 \oplus 2 \oplus 1 \oplus 2 \oplus 0 \\ = & \,3 \end{aligned}$

数据范围与规定

本题开启捆绑测试。

子任务编号 n≤n\le 特殊性质 分值
11 20002000 无 2020
22 10510^5 序列中 00 的个数 ≤1\le 1 1515
33 ^ 序列仅由 0,10,1 构成
44 无 2020
55 10610^6 ^ 3030

对于 100%100\% 的数据,1≤n≤1061\le n\le 10^6,0≤ai<n0\le a_i<n。