P10822 [EC Final 2020] Prof. Pang's sequence

庞教授得到一个固定的序列 $a_1, \ldots, a_n$ 和 $m$ 个查询。 每个查询由两个整数 $l$ 和 $r$ 指定，满足 $1\le l\le r\le n$。对于每个查询，你需要回答满足 $l\le i\le j\le r$ 且 $a_i, \ldots, a_j$ 中不同整数的数量为奇数的整数对 $(i, j)$ 的数量。

第一行包含一个整数 $n$ ($1\le n\le 5\times 10^5$)。 下一行包含 $n$ 个整数 $a_1, \ldots, a_n$ ($1\le a_i\le n$ 对于所有 $1\le i\le n$)，以单个空格分隔。 下一行包含一个整数 $m$ ($1\le m\le 5\times 10^5$)。 接下来的 $m$ 行中的每一行包含两个整数 $l$ 和 $r$ ($1\le l\le r\le n$)，以单个空格分隔，表示一个查询。

对于每个查询，输出一行，包含该查询的答案。

（由 ChatGPT 4o 翻译）