题解：CF1479B1 Painting the Array I

题面

原题目

一道典型的贪心题目。

根据 $seg$ 函数的定义可知，对于数组 $a$，$seg(a)=\sum_{i=1}^{n-1}(a_i \ne a_{i+1})$，为满足题目条件，应保证题面中 $a^{(0)}$ 和 $a^{(1)}$ 中的邻项尽可能不同。

对于一个正要被染色的元素 $a_i$，设当前 $a^{(0)}$ 的尾项为 $b_0$，$a^{(1)}$ 的尾项为 $b_1$，可以分为四种情况。

1. $b_0=a_i,b_1=a_i$。此时无论将 $a_i$ 染成哪个颜色，都不会对答案产生影响，也改变 $b_0$ 和 $b_1$ 的值，因此可以随意染色。
2. $b_0=a_i,b_1 \ne a_i$。此时如果将 $a_i$ 染上颜色 $0$，会对答案产生 $1$ 的贡献；而将 $a_i$ 染上颜色 $1$ 时，不改变答案且不改变 $b_1$。因此此时应染上颜色 $0$。
3. $b_0 \ne a_i,b_1=a_i$。此时应染上颜色 $1$，原理同上。
4. $b_0 \ne a_i,b_1 \ne a_i$。这时染上任意颜色都会产生贡献，考虑染上不同颜色对后面染色产生的影响。用 $nxt_{b_0}$ 表示与 $b_0$ 相同的元素在 $a$ 中下一次出现的位置，容易发现 $nxt_b$ 更小更容易遇到相同的元素，不利于产生贡献。于是将 $a_i$ 添加进 $nxt_b$ 更小的序列。

在这里放一个判断部分的代码好了。

  for(int i=1;i<=n;i++){
		if(a[i]==a[na]){
			if(a[i]!=a[nb])
				ans++;
			nb=i;
		}else if(a[i]==a[nb]){
			ans++;
			na=i;
		}else{
			ans++;
			if(nxt[na]<nxt[nb])
				na=i;
			else
				nb=i;
		}
	}