A16658 | Odd Queries on Odd Array
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
一个长度为 $m$ 的数组 $b$ 被称为可爱数组（cute），如果不存在四个下标 $1\le i < j < k < l \le m$，使得 $b_i\neq b_j$，$b_i = b_k$，并且 $b_j = b_l$。
我们定义长度为 $m$ 的数组 $b$ 的美丽值（beauty）为所有在 $b$ 中出现奇数次的不同数的和。形式化地，设 $\operatorname{cnt}(b, x)$ 表示 $x$ 在数组 $b$ 中出现的次数。那么，美丽值为
$$ \sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ 为奇数}}} x. $$
给定一个长度为 $n$ 的可爱数组 $a$，你需要在线回答 $q$ 个查询。每个查询包含两个整数 $l$ 和 $r$（$1\le l \le r \le n$），你需要计算子数组 $a_{l\ldots r}$ 的美丽值$^{\text{∗}}$。注意，查询是经过编码的，需要在得到前一个查询答案后才能解码下一个查询。
$^{\text{∗}}$ 子数组 $a_{l \ldots r}$ 指的是数组 $a$ 从第 $l$ 个元素到第 $r$ 个元素的连续区间，即 $[a_l, a_{l+1}, \ldots, a_r]$。
我们定义长度为 $m$ 的数组 $b$ 的美丽值（beauty）为所有在 $b$ 中出现奇数次的不同数的和。形式化地，设 $\operatorname{cnt}(b, x)$ 表示 $x$ 在数组 $b$ 中出现的次数。那么，美丽值为
$$ \sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ 为奇数}}} x. $$
给定一个长度为 $n$ 的可爱数组 $a$，你需要在线回答 $q$ 个查询。每个查询包含两个整数 $l$ 和 $r$（$1\le l \le r \le n$），你需要计算子数组 $a_{l\ldots r}$ 的美丽值$^{\text{∗}}$。注意，查询是经过编码的，需要在得到前一个查询答案后才能解码下一个查询。
$^{\text{∗}}$ 子数组 $a_{l \ldots r}$ 指的是数组 $a$ 从第 $l$ 个元素到第 $r$ 个元素的连续区间，即 $[a_l, a_{l+1}, \ldots, a_r]$。
输入格式
每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。每个测试用例的描述如下：
每个测试用例第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le 5\cdot 10^5$），分别表示数组 $a$ 的长度和查询的个数。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le n$），为可爱数组 $a$ 的元素。
接下来 $q$ 行，每行包含两个整数 $x'_i$ 和 $y'_i$（$1\le x'_i, y'_i\le n$），表示查询的区间端点（已编码）。
设 $\text{ans}_i$ 为第 $i$ 个查询的答案，$\text{ans}_0 = 0$。则 $x_i = ((x'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$，$y_i = ((y'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$。查询子数组的端点 $l_i$ 和 $r_i$ 解码为 $l_i = \min(x_i, y_i)$，$r_i = \max(x_i, y_i)$。
保证给定的数组 $a$ 满足可爱数组的条件。
保证所有测试用例的 $\sum n$ 和 $\sum q$ 不超过 $5\cdot 10^5$。
每个测试用例第一行包含两个整数 $n$ 和 $q$（$1\le n,q\le 5\cdot 10^5$），分别表示数组 $a$ 的长度和查询的个数。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le n$），为可爱数组 $a$ 的元素。
接下来 $q$ 行，每行包含两个整数 $x'_i$ 和 $y'_i$（$1\le x'_i, y'_i\le n$），表示查询的区间端点（已编码）。
设 $\text{ans}_i$ 为第 $i$ 个查询的答案，$\text{ans}_0 = 0$。则 $x_i = ((x'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$，$y_i = ((y'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$。查询子数组的端点 $l_i$ 和 $r_i$ 解码为 $l_i = \min(x_i, y_i)$，$r_i = \max(x_i, y_i)$。
保证给定的数组 $a$ 满足可爱数组的条件。
保证所有测试用例的 $\sum n$ 和 $\sum q$ 不超过 $5\cdot 10^5$。
输出格式
每个测试用例输出 $q$ 个整数，分别为每个查询的答案。
输入输出样例
输入 #1
3 11 4 1 1 2 2 3 3 3 2 2 1 1 7 10 5 11 8 6 2 8 6 2 1 3 2 3 4 3 1 6 1 4 3 6 3 3 3 1 1 1 2 3 1 2 2 2 3 3 3
输出 #1
4 5 4 0 10 6 3 0 3 3 0 3
在第一个测试用例中，查询如下：
- $$ x_1 = ((7 - 1 + 0) \bmod 11) + 1 = 7,\quad y_1 = ((10 - 1 + 0) \bmod 11) + 1 = 10 $$
$$ l_1 = \min(7, 10) = 7,\quad r_1 = \max(7, 10) = 10 $$
因此，查询的子数组为 $a_{7\ldots 10} = [3, 2, 2, 1]$。$3$ 和 $1$ 各出现 1 次（奇数），$2$ 出现 2 次（偶数）。所以美丽值为 $3 + 1 = 4$。
- $$ x_2 = ((5 - 1 + 4) \bmod 11) + 1 = 9, \quad y_2 = ((11 - 1 + 4) \bmod 11) + 1 = 4 $$
$$ l_2 = \min(9, 4) = 4,\quad r_2 = \max(9, 4) = 9 $$
查询的子数组为 $a_{4\ldots 9} = [2, 3, 3, 3, 2, 2]$。$2$ 和 $3$ 各出现 3 次（奇数）。美丽值为 $2 + 3 = 5$。
- $$ x_3 = ((8 - 1 + 5) \bmod 11) + 1 = 2,\quad y_3 = ((6 - 1 + 5) \bmod 11) + 1 = 11 $$
$$ l_3 = \min(2, 11) = 2,\quad r_3 = \max(2, 11) = 11 $$
查询的子数组为 $a_{2\ldots 11} = [1, 2, 2, 3, 3, 3, 2, 2, 1, 1]$。$1$ 和 $3$ 各出现 3 次（奇数），$2$ 出现 4 次（偶数）。美丽值为 $1 + 3 = 4$。
- $$ x_4 = ((2 - 1 + 4) \bmod 11) + 1 = 6,\quad y_4 = ((8 - 1 + 4) \bmod 11) + 1 = 1 $$
$$ l_4 = \min(6, 1) = 1,\quad r_4 = \max(6, 1) = 6 $$
查询的子数组为 $a_{1\ldots 6} = [1, 1, 2, 2, 3, 3]$。$1$、$2$、$3$ 都出现了 2 次（偶数）。美丽值为 $0$。
在第二个测试用例中，查询如下：
- $$ x_1 = ((1 - 1 + 0) \bmod 6) + 1 = 1,\quad y_1 = ((6 - 1 + 0) \bmod 6) + 1 = 6 $$
$$ l_1 = \min(1, 6) = 1,\quad r_1 = \max(1, 6) = 6 $$
查询子数组为 $a_{1\ldots 6} = [1, 3, 2, 3, 4, 3]$。$1$、$2$、$4$ 各出现 1 次（奇数），$3$ 出现 3 次（奇数）。美丽值为 $1 + 2 + 3 + 4 = 10$。
- $$ x_2 = ((1 - 1 + 10) \bmod 6) + 1 = 5,\quad y_2 = ((4 - 1 + 10) \bmod 6) + 1 = 2 $$
$$ l_2 = \min(5, 2) = 2,\quad r_2 = \max(5, 2) = 5 $$
查询子数组为 $a_{2\ldots 5} = [3, 2, 3, 4]$。$2$ 和 $4$ 各出现 1 次（奇数），$3$ 出现 2 次（偶数）。美丽值为 $2 + 4 = 6$。
在第三个测试用例中，数组 $a$ 的所有元素均为 $3$。
- 对于任意长度为奇数的子数组，$3$ 出现奇数次，因此美丽值为 $3$。
- 对于任意长度为偶数的子数组，$3$ 出现偶数次，因此美丽值为 $0$。
- $$ x_1 = ((7 - 1 + 0) \bmod 11) + 1 = 7,\quad y_1 = ((10 - 1 + 0) \bmod 11) + 1 = 10 $$
$$ l_1 = \min(7, 10) = 7,\quad r_1 = \max(7, 10) = 10 $$
因此，查询的子数组为 $a_{7\ldots 10} = [3, 2, 2, 1]$。$3$ 和 $1$ 各出现 1 次（奇数），$2$ 出现 2 次（偶数）。所以美丽值为 $3 + 1 = 4$。
- $$ x_2 = ((5 - 1 + 4) \bmod 11) + 1 = 9, \quad y_2 = ((11 - 1 + 4) \bmod 11) + 1 = 4 $$
$$ l_2 = \min(9, 4) = 4,\quad r_2 = \max(9, 4) = 9 $$
查询的子数组为 $a_{4\ldots 9} = [2, 3, 3, 3, 2, 2]$。$2$ 和 $3$ 各出现 3 次（奇数）。美丽值为 $2 + 3 = 5$。
- $$ x_3 = ((8 - 1 + 5) \bmod 11) + 1 = 2,\quad y_3 = ((6 - 1 + 5) \bmod 11) + 1 = 11 $$
$$ l_3 = \min(2, 11) = 2,\quad r_3 = \max(2, 11) = 11 $$
查询的子数组为 $a_{2\ldots 11} = [1, 2, 2, 3, 3, 3, 2, 2, 1, 1]$。$1$ 和 $3$ 各出现 3 次（奇数），$2$ 出现 4 次（偶数）。美丽值为 $1 + 3 = 4$。
- $$ x_4 = ((2 - 1 + 4) \bmod 11) + 1 = 6,\quad y_4 = ((8 - 1 + 4) \bmod 11) + 1 = 1 $$
$$ l_4 = \min(6, 1) = 1,\quad r_4 = \max(6, 1) = 6 $$
查询的子数组为 $a_{1\ldots 6} = [1, 1, 2, 2, 3, 3]$。$1$、$2$、$3$ 都出现了 2 次（偶数）。美丽值为 $0$。
在第二个测试用例中，查询如下：
- $$ x_1 = ((1 - 1 + 0) \bmod 6) + 1 = 1,\quad y_1 = ((6 - 1 + 0) \bmod 6) + 1 = 6 $$
$$ l_1 = \min(1, 6) = 1,\quad r_1 = \max(1, 6) = 6 $$
查询子数组为 $a_{1\ldots 6} = [1, 3, 2, 3, 4, 3]$。$1$、$2$、$4$ 各出现 1 次（奇数），$3$ 出现 3 次（奇数）。美丽值为 $1 + 2 + 3 + 4 = 10$。
- $$ x_2 = ((1 - 1 + 10) \bmod 6) + 1 = 5,\quad y_2 = ((4 - 1 + 10) \bmod 6) + 1 = 2 $$
$$ l_2 = \min(5, 2) = 2,\quad r_2 = \max(5, 2) = 5 $$
查询子数组为 $a_{2\ldots 5} = [3, 2, 3, 4]$。$2$ 和 $4$ 各出现 1 次（奇数），$3$ 出现 2 次（偶数）。美丽值为 $2 + 4 = 6$。
在第三个测试用例中，数组 $a$ 的所有元素均为 $3$。
- 对于任意长度为奇数的子数组，$3$ 出现奇数次，因此美丽值为 $3$。
- 对于任意长度为偶数的子数组，$3$ 出现偶数次，因此美丽值为 $0$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？