CF633H Fibonacci-ish II

Yash 终于厌倦了计算最长“类斐波那契序列”的长度，现在他开始玩更复杂的事情，比如“类斐波那契势能”。 数组 $a_{i}$ 的类斐波那契势能的计算方式如下： 1. 对于所有存在 $i < j$ 且 $a_{i} = a_{j}$ 的元素 $j$，移除所有这样的 $j$。 2. 对剩下的元素按升序排序，即 $a_{1} < a_{2} < \dots < a_{n}$。 3. 势能的计算方法为 $P(a) = a_{1} · F_{1} + a_{2} · F_{2} + \dots + a_{n} · F_{n}$，其中 $F_{i}$ 表示第 $i$ 个斐波那契数（具体见提示）。 现给定一个长度为 $n$ 的数组 $a_{i}$，以及 $q$ 个区间 $[l_{j}, r_{j}]$。对于每个区间 $j$，请计算用 $a_{i}$ 的 $l_{j}$ 到 $r_{j}$ 区间内所有元素组成的新数组 $b_{i}$ 的类斐波那契势能，并对 $m$ 取模。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 30000$）——初始数组的长度以及模数。 第二行包含 $n$ 个整数 $a_{i}$（$0 \leq a_{i} \leq 10^{9}$）——数组的元素。 接下来一行包含区间个数 $q$（$1 \leq q \leq 30000$）。 接下来 $q$ 行，每行包含一对整数 $l_{i}$ 和 $r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$）——表示每次查询的区间。

输出共 $q$ 行，第 $i$ 行输出第 $i$ 个区间对应的类斐波那契势能对 $m$ 取模后的结果。

本题中，斐波那契数的定义如下： 1. $F_{1} = F_{2} = 1$。 2. 对于每个 $n > 2$，有 $F_{n} = F_{n-1} + F_{n-2}$。 例如，对于第一个查询，子数组为 $[1,2,1]$，其元素集合为 $\{1, 2\}$，所以该子数组的势能为 $1 \times 1 + 2 \times 1 = 3$。 由 ChatGPT 5 翻译