P1052序列询问（mock1query）

【题目描述】

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，其中对于所有 $1\leq i\leq n$，均有 $a_i\in\{0,1\}$。

对于任意一个只包含 $0,1$ 的序列 $S=(s_1,s_2,\ldots,s_k)$，从左到右依次扫描其中的元素。初始时栈为空。若栈非空且当前元素与栈顶元素相同，则弹出栈顶，否则将当前元素压入栈中。扫描结束后，将栈中元素从栈底到栈顶依次排列，得到的消除结果记为 $\text{red}(S)$。

例如，当 $S=(0,1,1,0)$ 时，栈中的元素依次变化为 $\varnothing\longrightarrow0\longrightarrow01\longrightarrow0\longrightarrow\varnothing$，因此 $\text{red}(S)=\varnothing$。

有 $q$ 次询问，其中第 $j$ 次询问给出两个整数 $l_j,r_j$。对于每个满足 $l_j\leq m<r_j$ 的整数 $m$，定义左侧序列 $L_{j,m}=(a_{l_j},a_{l_j+1},\ldots,a_m)$，右侧序列 $R_{j,m}=(a_{m+1},a_{m+2},\ldots,a_{r_j})$。

对于两个序列 $A,B$，记 $A\circ B$ 表示将 $B$ 接在 $A$ 后得到的序列。先分别求出 $\text{red}(L_{j,m})$ 与 $\text{red}(R_{j,m})$，再将二者拼接，得到 $C_{j,m}=\text{red}(L_{j,m})\circ\text{red}(R_{j,m})$。

此后继续消除 $C_{j,m}$。这一阶段新消除的元素对数称为分割点 $m$ 的拼接消除次数，记为

特别地，分别计算 $\text{red}(L_{j,m})$ 与 $\text{red}(R_{j,m})$ 时发生的消除不计入 $f_j(m)$。

对于每次询问，你需要求出所有分割点的拼接消除次数之和，即

【输入格式】

从文件 $\textbf{\textit{query.in}}$ 中读入数据。

本题有多组测试数据。

输入的第一行包含两个整数 $c,T$，分别表示测试点编号和测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

• 第一行包含两个正整数 $n,q$，分别表示序列长度与询问次数。
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，描述给定的序列。
• 接下来 $q$ 行，每行包含两个整数 $l,r$，表示一次询问的区间。

【输出格式】

输出到文件 $\textbf{\textit{query.out}}$ 中。

对于每次询问，输出一行一个非负整数，表示所有分割点的拼接消除次数之和。

【样例 1 输入】

10 125 330 1 1 0 141 451 562 5

【样例 1 输出】

142431

【说明/提示】

【样例 1 解释】

考虑第一次询问 $[1,4]$。

当 $m=1$ 时，$\text{red}(L_{1,1})=(0)$，$\text{red}(R_{1,1})=(0)$，因此 $f_1(1)=1$。

当 $m=2$ 时，$\text{red}(L_{1,2})=(0,1)$，$\text{red}(R_{1,2})=(1,0)$，因此 $f_1(2)=2$。

当 $m=3$ 时，$\text{red}(L_{1,3})=(0)$，$\text{red}(R_{1,3})=(0)$，因此 $f_1(3)=1$。

因此，这次询问的答案为 $1+2+1=4$。

【样例 2】

见选手目录下的 $\textbf{\textit{query/query2.in}}$ 和 $\textbf{\textit{query/query2.ans}}$。

该附加样例满足测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{query/query3.in}}$ 和 $\textbf{\textit{query/query3.ans}}$。

该附加样例满足测试点 $7\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{query/query4.in}}$ 和 $\textbf{\textit{query/query4.ans}}$。

该附加样例满足测试点 $10\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{query/query5.in}}$ 和 $\textbf{\textit{query/query5.ans}}$。

该附加样例满足测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于所有测试数据，保证：

• $0\leq c\leq20$。
• $1\leq T\leq10$。
• 对于每组测试数据，均有 $2\leq n\leq10^5$，$1\leq q\leq10^5$。
• 对于单个测试点内的所有测试数据，保证 $\sum n\leq10^5$，$\sum q\leq10^5$。
• 对于所有 $1\leq i\leq n$，均有 $a_i\in\{0,1\}$。
• 对于每次询问，均有 $1\leq l<r\leq n$。