CF1766E Decomposition

对于一个整数序列 $[x_1, x_2, \dots, x_k]$，我们定义其分解方式如下： 从第一个元素到最后一个元素依次处理，维护其子序列的列表。当处理元素 $x_i$ 时，将其追加到列表中第一个满足其最后一个元素与 $x_i$ 的按位与大于 $0$ 的子序列末尾。如果没有这样的子序列，则新建一个仅包含 $x_i$ 的子序列，并将其追加到子序列列表末尾。 例如，分析序列 $[1, 3, 2, 0, 1, 3, 2, 1]$ 的分解过程： - 处理元素 $1$，子序列列表为空。没有可以追加 $1$ 的子序列，因此新建子序列 $[1]$； - 处理元素 $3$，子序列列表为 $[[1]]$。$3$ 与 $1$ 的按位与为 $1$，因此将其追加到第一个子序列； - 处理元素 $2$，子序列列表为 $[[1, 3]]$。$2$ 与 $3$ 的按位与为 $2$，因此将其追加到第一个子序列； - 处理元素 $0$，子序列列表为 $[[1, 3, 2]]$。没有可以追加 $0$ 的子序列，因此新建子序列 $[0]$； - 处理元素 $1$，子序列列表为 $[[1, 3, 2], [0]]$。没有可以追加 $1$ 的子序列，因此新建子序列 $[1]$； - 处理元素 $3$，子序列列表为 $[[1, 3, 2], [0], [1]]$。$3$ 与 $2$ 的按位与为 $2$，因此将其追加到第一个子序列； - 处理元素 $2$，子序列列表为 $[[1, 3, 2, 3], [0], [1]]$。$2$ 与 $3$ 的按位与为 $2$，因此将其追加到第一个子序列； - 处理元素 $1$，子序列列表为 $[[1, 3, 2, 3, 2], [0], [1]]$。$1$ 不能追加到前两个子序列，但可以追加到第三个子序列。 最终得到的子序列列表为 $[[1, 3, 2, 3, 2], [0], [1, 1]]$。 记 $f([x_1, x_2, \dots, x_k])$ 为序列 $[x_1, x_2, \dots, x_k]$ 被分解成的子序列个数。 现在，正式的问题如下： 给定一个序列 $[a_1, a_2, \dots, a_n]$，其中每个元素都是 $0$ 到 $3$ 之间的整数。记 $a[i..j]$ 为序列 $[a_i, a_{i+1}, \dots, a_j]$。你需要计算 $\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$。

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 3$）。

输出一个整数，表示 $\sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j])$ 的值。

由 ChatGPT 4.1 翻译