← 返回题目列表

Codeforces · 2152/C

C. 三重去除

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

厌倦了支持范围进位,Keria 现在正在创建一个关于支持范围查询的数据结构问题。

对于长度为 $$$m$$$ 的数组 $$$b = [b_1, b_2, \ldots, b_m]$$$,其中 $$$b_i=0$$$ 或 $$$b_i=1$$$,请考虑以下内容 三重删除 操作:

  1. 选择三个索引 $$$1 \le i \lt j \lt k \le m$$$ 使得这些位置的元素相同 ($$$b_i = b_j = b_k$$$)。
  2. 从数组中删除这三个元素。该操作的成本定义为$$$\min(k-j, j-i)$$$。删除后,数组的剩余部分将被连接起来,并重新标记它们的索引。

我们希望使用以下命令将数组 $$$b$$$ 清空 三重删除 操作。因此,我们定义 总成本 数组的 作为以下成本的最小可能总和 将数组清空所需的 三重删除 操作。如果不可能使数组为空,则成本定义为$$$-1$$$。

Keria 想测试他的数据结构。为此,您必须回答 $$$q$$$ 独立查询。最初,给定一个数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,长度为 $$$n$$$,其中 $$$a_i=0$$$ 或 $$$a_i=1$$$。对于每个查询,您都会获得一个范围 $$$1 \le l \le r \le n$$$,并且必须找到数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 的成本。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 250\,000$$$) - 数组的长度和查询的数量。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$($$$a_i = 0$$$ 或 $$$a_i=1$$$)— 数组的元素。

然后是 $$$q$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) - 第 $$$i$$$ 查询的子数组范围。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个测试用例,输出 $$$q$$$ 行。第 $$$i$$$ 行应包含一个整数,表示第 $$$i$$$ 查询的答案。

示例

输入
复制

2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6

输出
复制

4
2
3
-1
1
1
2

注意

第一个测试用例的解释,第一个查询(1 12):

子数组为 $$$[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$$$。有六个 $$$0$$$ 和六个 $$$1$$$。可能的最佳操作顺序是:

  1. 删除索引 $$$3$$$、$$$4$$$、$$$6$$$ 处的三个 $$$1$$$。成本为 $$$\min(6-4, 4-3) = \min(2, 1) = 1$$$。该数组变为 $$$[0, 0, 0, 0, 1, 0, 1, 1, 0]$$$。
  2. 删除索引 $$$1$$$、$$$2$$$、$$$3$$$ 处的三个 $$$0$$$。成本为 $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$。该数组变为 $$$[0, 1, 0, 1, 1, 0]$$$。
  3. 删除索引 $$$2$$$、$$$4$$$、$$$5$$$ 处的三个 $$$1$$$。成本为 $$$\min(5-4, 4-2) = \min(1, 2) = 1$$$。该数组变为 $$$[0, 0, 0]$$$。
  4. 删除索引 $$$1$$$、$$$2$$$、$$$3$$$ 处的三个 $$$0$$$。成本为 $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$。数组现在是空的。

总成本为$$$1+1+1+1=4$$$。