← 返回题目列表

Codeforces · 2153/F

F. 奇数组上的奇查询

中文机器翻译题面 查看原题

长度为 $$$m$$$ 的数组 $$$b$$$ 为 可爱 如果不存在四个索引 $$$1\le i \lt j \lt k \lt l \le m$$$ 使得 $$$b_i\neq b_j$$$、$$$b_i = b_k$$$ 和 $$$b_j = b_l$$$。

的 美女 长度为 $$$m$$$ 的数组 $$$b$$$ 的 定义为数组 $$$b$$$ 中出现奇数次的所有不同值的总和。形式上,令 $$$\operatorname{cnt}(b, x)$$$ 表示值 $$$x$$$ 在数组 $$$b$$$ 中出现的次数。那么,美感由 $$\sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ is odd}}}x.$$ 给出

给你一个可爱的数组$$$a$$$,长度为$$$n$$$,你需要在线回答$$$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$$$ 行的第 $$$i$$$ 行包含两个整数 $$$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$$$。第 $$$i$$$ 查询子数组的端点 $$$l_i$$$ 和 $$$r_i$$$ 被解码为 $$$l_i = \min(x_i, y_i)$$$ 和 $$$r_i = \max(x_i, y_i)$$$。

保证给定的数组 $$$a$$$ 满足可爱数组的条件。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数表示每个查询的答案。

示例

输入
复制

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

输出
复制

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$$$ 出现一次(奇数),值 $$$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$$$ 各出现两次(偶数)。因此,美丽是$$$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$$$ 出现一次(奇数),值 $$$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$$$ 出现一次(奇数),值 $$$3$$$ 出现两次(偶数)。因此,美丽是$$$2 + 4 = 6$$$。

在第三个测试用例中,数组 $$$a$$$ 的所有元素都等于 $$$3$$$。

  • 对于任何奇数长度的子数组,值 $$$3$$$ 出现奇数次,因此美丽度为 $$$3$$$。
  • 对于任何偶数长度的子数组,值 $$$3$$$ 出现偶数次,因此美丽的是 $$$0$$$。