#PQJ963x4405. QOJ 963_4405

    ID: 3076 传统题 15000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2022线段树

QOJ 963_4405

标题: 普罗霍洛夫卡 - Problem - QOJ.ac

#4405. 普罗霍洛夫卡

Statistics

The problem was used in the following contests:

Time Limit: 10s → 15s

题目描述

给定序列 a1,…,an,共 m 次询问,每次询问给出 l,r,查询所有满足 l≤L≤R≤r 的 (L,R) 的权值的按位异或和,二元组 (L,R) 的权值是 |{ai∣L≤i≤R}|。

输入格式

从标准输入读入数据。

第一行两个整数 n m;

接下来一行 n 个整数 a1,…,an;

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

输出格式

输出到标准输出。

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

样例数据

样例 1 输入

5 2
1 1 1 2 4
1 5
3 5

样例 1 输出

3
2

子任务

对于 5% 的数据,满足 1≤n,m≤100。

对于 10% 的数据,满足 1≤n,m≤5000。

对于 20% 的数据,满足 1≤n,m≤105。

对于 30% 的数据,满足 1≤n,m≤2×105。

对于 40% 的数据,满足 1≤n,m≤3×105。

对于 50% 的数据,满足 1≤n,m≤3.5×105。

对于另外 10% 的数据,满足 m=n2。

对于另外 10% 的数据,满足对任意 i=1⋯n,ai≤2。

对于另外 10% 的数据,满足对任意 i=1⋯n,ai≤10。

对于 100% 的数据,满足 1≤n,m≤4×105,1≤ai≤n,所有数值为整数。

每类数据构成子任务。