307676: CF1394E. Boboniu and Banknote Collection
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Boboniu and Banknote Collection
题意翻译
**简要题意**:求长为 $n$ 的序列 $a$ 的所有前缀的最大折叠次数。 形式化来讲:设 $b$ 是 $a$ 的一个折叠序列,那么 $b$ 需要满足: - $\forall 1\le i\le n$,$b_i\in\{1,-1\}$。 - 设 $p(i)=[b_i=1]+\sum_{j=1}^{i-1}b_j$,对于任意的 $i,j$ 满足 $1\le i<j\le n$,若 $p(i)=p(j)$,则必须有 $a_i=a_j$。 给你一个长为 $n$ 的序列 $a$,对于 $a$ 的所有前缀 $[a_1,a_2,\cdots,a_i]$,你需要求出: - $[a_1,a_2,\cdots,a_i]$ 的所有折叠序列 $b$ 中,$\sum_{j=1}^{i-1}[b_j\ne b_{j+1}]$ 的最大值。 #### 数据范围 $1\le a_i\le n\le10^5$。题目描述
No matter what trouble you're in, don't be afraid, but face it with a smile. I've made another billion dollars! — Boboniu Boboniu has issued his currencies, named Bobo Yuan. Bobo Yuan (BBY) is a series of currencies. Boboniu gives each of them a positive integer identifier, such as BBY-1, BBY-2, etc. Boboniu has a BBY collection. His collection looks like a sequence. For example: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1394E/af5ca1ff6453d4700bd6b890ce1c8859d023ad2b.png)We can use sequence $ a=[1,2,3,3,2,1,4,4,1] $ of length $ n=9 $ to denote it. Now Boboniu wants to fold his collection. You can imagine that Boboniu stick his collection to a long piece of paper and fold it between currencies: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1394E/874b77ee60693cdb02072ea946ee0568b1eda880.png)Boboniu will only fold the same identifier of currencies together. In other words, if $ a_i $ is folded over $ a_j $ ( $ 1\le i,j\le n $ ), then $ a_i=a_j $ must hold. Boboniu doesn't care if you follow this rule in the process of folding. But once it is finished, the rule should be obeyed. A formal definition of fold is described in notes. According to the picture above, you can fold $ a $ two times. In fact, you can fold $ a=[1,2,3,3,2,1,4,4,1] $ at most two times. So the maximum number of folds of it is $ 2 $ . As an international fan of Boboniu, you're asked to calculate the maximum number of folds. You're given a sequence $ a $ of length $ n $ , for each $ i $ ( $ 1\le i\le n $ ), you need to calculate the maximum number of folds of $ [a_1,a_2,\ldots,a_i] $ .输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1\le n\le 10^5 $ ). The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1\le a_i\le n $ ).
输出格式
Print $ n $ integers. The $ i $ -th of them should be equal to the maximum number of folds of $ [a_1,a_2,\ldots,a_i] $ .
输入输出样例
输入样例 #1
9
1 2 3 3 2 1 4 4 1
输出样例 #1
0 0 0 1 1 1 1 2 2
输入样例 #2
9
1 2 2 2 2 1 1 2 2
输出样例 #2
0 0 1 2 3 3 4 4 5
输入样例 #3
15
1 2 3 4 5 5 4 3 2 2 3 4 4 3 6
输出样例 #3
0 0 0 0 0 1 1 1 1 2 2 2 3 3 0
输入样例 #4
50
1 2 4 6 6 4 2 1 3 5 5 3 1 2 4 4 2 1 3 3 1 2 2 1 1 1 2 4 6 6 4 2 1 3 5 5 3 1 2 4 4 2 1 3 3 1 2 2 1 1
输出样例 #4
0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 4 5 5 6 7 3 3 3 4 4 4 4 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8