Decomposition

题意翻译

对于 $n$ 个数 $x_1,x_2,...,x_n$，定义其拆分为： 从 $1$ 到 $n$ 的顺序遍历 $x_1,x_2,...,x_n$。 设当前遍历到 $x_i$： * 如果当前没有序列或者任何一个序列的结尾 $\operatorname{AND}$（按位与）$x_i$ 都为 $0$，那么新开一个序列，新序列中只包含这一个值。 * 否则找到第一个结尾 $\operatorname{AND}\space x_i$ 不为 $0$ 的序列，把 $x_i$ 加在其结尾。 设 $f([x_1,x_2,...,x_n])$ 为拆分得到序列的个数。给出 $a_1,a_2,...,a_n$，求 $\sum_{i=1}^n\sum_{j=i}^nf([a_i,a_{i+1},...,a_j])$。

题目描述

For a sequence of integers $ [x_1, x_2, \dots, x_k] $ , let's define its decomposition as follows: Process the sequence from the first element to the last one, maintaining the list of its subsequences. When you process the element $ x_i $ , append it to the end of the first subsequence in the list such that the bitwise AND of its last element and $ x_i $ is greater than $ 0 $ . If there is no such subsequence in the list, create a new subsequence with only one element $ x_i $ and append it to the end of the list of subsequences. For example, let's analyze the decomposition of the sequence $ [1, 3, 2, 0, 1, 3, 2, 1] $ : - processing element $ 1 $ , the list of subsequences is empty. There is no subsequence to append $ 1 $ to, so we create a new subsequence $ [1] $ ; - processing element $ 3 $ , the list of subsequences is $ [[1]] $ . Since the bitwise AND of $ 3 $ and $ 1 $ is $ 1 $ , the element is appended to the first subsequence; - processing element $ 2 $ , the list of subsequences is $ [[1, 3]] $ . Since the bitwise AND of $ 2 $ and $ 3 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 0 $ , the list of subsequences is $ [[1, 3, 2]] $ . There is no subsequence to append $ 0 $ to, so we create a new subsequence $ [0] $ ; - processing element $ 1 $ , the list of subsequences is $ [[1, 3, 2], [0]] $ . There is no subsequence to append $ 1 $ to, so we create a new subsequence $ [1] $ ; - processing element $ 3 $ , the list of subsequences is $ [[1, 3, 2], [0], [1]] $ . Since the bitwise AND of $ 3 $ and $ 2 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 2 $ , the list of subsequences is $ [[1, 3, 2, 3], [0], [1]] $ . Since the bitwise AND of $ 2 $ and $ 3 $ is $ 2 $ , the element is appended to the first subsequence; - processing element $ 1 $ , the list of subsequences is $ [[1, 3, 2, 3, 2], [0], [1]] $ . The element $ 1 $ cannot be appended to any of the first two subsequences, but can be appended to the third one. The resulting list of subsequences is $ [[1, 3, 2, 3, 2], [0], [1, 1]] $ . Let $ f([x_1, x_2, \dots, x_k]) $ be the number of subsequences the sequence $ [x_1, x_2, \dots, x_k] $ is decomposed into. Now, for the problem itself. You are given a sequence $ [a_1, a_2, \dots, a_n] $ , where each element is an integer from $ 0 $ to $ 3 $ . Let $ a[i..j] $ be the sequence $ [a_i, a_{i+1}, \dots, a_j] $ . You have to calculate $ \sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j]) $ .

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 3 $ ).

输出格式

Print one integer, which should be equal to $ \sum \limits_{i=1}^n \sum \limits_{j=i}^n f(a[i..j]) $ .

输入输出样例

输入样例 #1

8
1 3 2 0 1 3 2 1

输出样例 #1

71

输入样例 #2

5
0 0 0 0 0

输出样例 #2

35

**题目大意**：

对于一串整数序列 $[x_1, x_2, \dots, x_k]$，定义其拆分如下：

从第一个元素到最后一个元素遍历序列，维护其子序列的列表。当处理元素 $x_i$ 时，将其添加到列表中第一个子序列的末尾，使得该子序列的最后一个元素与 $x_i$ 的按位与结果大于 0。如果列表中没有这样的子序列，则创建一个新的只包含一个元素 $x_i$ 的子序列，并将其添加到子序列列表的末尾。

定义 $f([x_1, x_2, \dots, x_k])$ 为序列 $[x_1, x_2, \dots, x_k]$ 拆分得到的子序列个数。

给定一个序列 $[a_1, a_2, \dots, a_n]$，其中每个元素都是介于 0 到 3 之间的整数。计算 $\sum_{i=1}^n \sum_{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_{i=1}^n \sum_{j=i}^n f(a[i..j])$。

**输入输出样例**：

**输入样例 #1**：
```
8
1 3 2 0 1 3 2 1
```

**输出样例 #1**：
```
71
```

**输入样例 #2**：
```
5
0 0 0 0 0
```

**输出样例 #2**：
```
35
```**题目大意**： 对于一串整数序列 $[x_1, x_2, \dots, x_k]$，定义其拆分如下： 从第一个元素到最后一个元素遍历序列，维护其子序列的列表。当处理元素 $x_i$ 时，将其添加到列表中第一个子序列的末尾，使得该子序列的最后一个元素与 $x_i$ 的按位与结果大于 0。如果列表中没有这样的子序列，则创建一个新的只包含一个元素 $x_i$ 的子序列，并将其添加到子序列列表的末尾。 定义 $f([x_1, x_2, \dots, x_k])$ 为序列 $[x_1, x_2, \dots, x_k]$ 拆分得到的子序列个数。 给定一个序列 $[a_1, a_2, \dots, a_n]$，其中每个元素都是介于 0 到 3 之间的整数。计算 $\sum_{i=1}^n \sum_{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_{i=1}^n \sum_{j=i}^n f(a[i..j])$。 **输入输出样例**： **输入样例 #1**： ``` 8 1 3 2 0 1 3 2 1 ``` **输出样例 #1**： ``` 71 ``` **输入样例 #2**： ``` 5 0 0 0 0 0 ``` **输出样例 #2**： ``` 35 ```