QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB

# 7440. rsxc

统计

给定一个长为 $n$($1\le n\le 6\times 10^5$)的非负整数序列 $a_0,a_1,\dots,a_{n-1}$($0\le a_i < 2^{30}$)。

有 $q$ 个询问($1\le q\le 10^6$)。

每次询问给出两个整数 $l,r$($0\le l\le r < n$),求有多少对整数 $(x,y)$ 满足:

  • $l\le x\le y\le r$;
  • $\forall i,j\in S\ :i\oplus j\in S$,其中 $S:=\{a_k\}_{k=x}^y$。

实现细节

由于本题数据较多,您不需要输入输出,请完善以下程序中的 init(int, int, vector<int>)solve(int, int) 函数,并提交。

void init(int n, int q, vector<int> a) {
  // implement...
}

long long solve(int l, int r) {
  // implement...
}

你可以在下发文件中得到本题的样例交互库。

样例数据

样例 1 输入

5 10 2
0000000001000020000300004

样例 1 输出

4834712607666044912

样例 2 输入

20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>

样例 2 输出

5449866856465492064

子任务

Idea:Powerless,Solution:ccz181078&noip&w33z,Code:w33z,Data:w33z

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