Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB
Statistics

题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1,\cdots,a_n$。

统计二元组 $(i,j)$ 的数量,满足 $1\leq i\leq j\leq n$ 且 $a_i\oplus a_{i+1}\oplus \cdots\oplus a_j\leq \max\{a_i,a_{i+1}\cdots,a_j\}$,其中 $\oplus$ 是按位异或。

输入格式

输入数据第一行包含一个整数 $n$。

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

输出格式

输出一行一个整数表示合法的二元组 $(i,j)$ 的数量。

样例

样例输入 1

4
1 2 4 3

样例输出 1

5

样例 2~3

见下发文件。

数据范围

  • 对于前 $20\%$ 的数据,$n\leq 2\times 10^3$。
  • 对于另外 $20\%$ 的数据,$a_i<8$。
  • 对于另外 $20\%$ 的数据,$a_1\leq a_2\leq \cdots\leq a_n$。
  • 对于另外 $20\%$ 的数据,$a_i$ 在 $[0,2^{30})$ 范围内均匀随机生成。

对于 $100\%$ 的数据,$1\leq n\leq 10^5$,$0\leq a_i<2^{30}$。