Time Limit: 10s → 15s

题目描述

给定序列 $a_1,\dots,a_n$，共 $m$ 次询问，每次询问给出 $l,r$，查询所有满足 $l\le L\le R\le r$ 的 $(L,R)$ 的权值的按位异或和，二元组 $(L,R)$ 的权值是 $|\{a_i\mid L\le i\le R\}|$。

输入格式

从标准输入读入数据。

第一行两个整数 $n\ m$；

接下来一行 $n$ 个整数 $a_1,\dots,a_n$；

接下来 $m$ 行，每行两个整数 $l\ r$ 表示一次查询。

输出格式

输出到标准输出。

输出 $m$ 行，依次表示每个询问的答案。

样例数据

样例 1 输入

5 2
1 1 1 2 4
1 5
3 5

样例 1 输出

3
2

子任务

对于 $5\%$ 的数据，满足 $1\le n,m\le 100$。

对于 $10\%$ 的数据，满足 $1\le n,m\le 5000$。

对于 $20\%$ 的数据，满足 $1\le n,m\le 10^5$。

对于 $30\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$。

对于 $40\%$ 的数据，满足 $1\le n,m\le 3\times 10^5$。

对于 $50\%$ 的数据，满足 $1\le n,m\le 3.5\times 10^5$。

对于另外 $10\%$ 的数据，满足 $m=n^2$。

对于另外 $10\%$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 2$。

对于另外 $10\%$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 10$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 4\times 10^5$，$1\le a_i\le n$，所有数值为整数。

每类数据构成子任务。