CF2152C Triple Removal

Keria 厌倦了为远程输出型英雄提供支援，现在她设计了一个关于支持区间查询的数据结构问题。 对于一个长度为 $m$ 的数组 $b = [b_1, b_2, \ldots, b_m]$，其中 $b_i=0$ 或 $b_i=1$，定义如下的“三元组移除”操作： 1. 选择三个下标 $1 \le i < j < k \le m$，使得这三个位置上的元素相同（即 $b_i = b_j = b_k$）。 2. 将这三个元素从数组中移除。该操作的代价为 $\min(k-j, j-i)$。移除后，剩余的数组连接起来，重新编号。 我们的目标是通过三元组移除操作，将数组 $b$ 变为空。数组的总代价定义为：将数组清空所需一系列三元组移除操作代价之和的最小值。如果无法将数组清空，则代价定义为 $-1$。 Keria 希望测试她的数据结构。为此，你需要回答 $q$ 个相互独立的查询。最初你会得到一个长度为 $n$ 的数组 $a = [a_1, a_2, \ldots, a_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$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 次查询的区间。 保证所有测试数据中 $n$ 之和不超过 $250\,000$，$q$ 之和不超过 $250\,000$。

对于每组测试数据，输出 $q$ 行，每行一个整数，为第 $i$ 个查询的答案。

第一组样例，第一条查询（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$。 由 ChatGPT 5 翻译