CF1479B1 Painting the Array I
CF1479B1 Painting the Array II

题意：

本题与 CF1480D2 的唯一区别是本题询问最大可能解.

给 定 一 个 数 组 a , 你 将 a i 染 为 b i 色 , 其 中 b 是 由 你 指 定 的 一 个 01 数 组 . 将 a 数 组 中 被 染 成 0 色 的 数 字 取 出 来 并 依 在 a 中 出 现 的 顺 序 排 列 , 组 成 数 组 a ( 0 ) . 同 理 , 将 a 数 组 中 被 染 成 1 色 的 数 字 取 出 来 并 依 在 a 中 出 现 的 顺 序 排 列 , 组 成 数 组 a ( 1 ) . 给定一个数组 a, 你将 a_i染为 b_i色, 其中 b 是由你指定的一个 01 数组. 将 a 数组中被染成 0 色的数字取出来并依在 a 中出现的顺序排列, 组成数组 a^{(0)}. 同理, 将 a 数组中被染成 1 色的数字取出来并依在 a 中出现的顺序排列, 组成数组 a^{(1)}. 给定一个数组a,你将ai​染为bi​色,其中b是由你指定的一个01数组.将a数组中被染成0色的数字取出来并依在a中出现的顺序排列,组成数组a(0).同理,将a数组中被染成1色的数字取出来并依在a中出现的顺序排列,组成数组a(1).

我 们 定 义 s e g ( c ) 是 一 个 正 整 数 , 其 中 c 是 一 个 数 组 , s e g ( c ) 的 值 为 在 我 们 将 c 中 相 邻 的 所 有 相 同 元 素 合 并 后 , c 数 组 的 大 小 . 例 如 , s e g ( [ 1 , 1 , 4 , 5 , 1 , 4 ] ) = ∣ [ 1 , 4 , 5 , 1 , 4 ] ∣ = 5. 最 大 化 s e g ( a ( 0 ) ) + s e g ( a ( 1 ) ) 我们定义 seg(c) 是一个正整数, 其中 c 是一个数组, seg(c) 的值为在我们将 c 中相邻的所有相同元素合并后, c 数组的大小. 例如, seg([1, 1, 4, 5, 1, 4]) = |[1, 4, 5, 1, 4]|=5. 最大化 seg(a^{(0)})+seg(a^{(1)}) 我们定义seg(c)是一个正整数,其中c是一个数组,seg(c)的值为在我们将c中相邻的所有相同元素合并后,c数组的大小.例如,seg([1,1,4,5,1,4])=∣[1,4,5,1,4]∣=5.最大化seg(a(0))+seg(a(1))

题解：

贪心策略，问题D1，如果我们想让值更大，就要尽可能避免相同数字相邻的情况，现在有两数组 a 0 a^0 a0和 a 1 a^1 a1,那么我们可以这样把其当作栈，分配数组a时，尽可能让相同元素岔开

1. 如果第一个栈顶==第二个栈顶，那ai随便放一边都行，
2. 如果第一个栈顶!=第二个，且第一个栈顶= a i a_{i} ai​，那么就把ai放在另一个栈中
3. 如果第一个栈顶!=第二个，且第二个栈顶= a i a_{i} ai​，那么就把ai放在另一个栈中
4. 如果两个栈都不等于ai,且两个栈顶也不一样，貌似此时怎么放都行？但并不是因为我们所放的位置会影响后面的决定，因为放完就成为新的栈顶了。此时我们引入nxt数组，nxt[x]表示下一个 a x a_{x} ax​的位置。我们比较两个栈顶的nxt，越小说明相同元素再出现越接近，就更需要我们用不同的元素去隔开

D2问题就是反过来统计答案

代码：

D1

#include <bits/stdc++.h>
#include <unordered_map>
#define debug(a, b) printf("%s = %d\n", a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll= 1e18;
const int INF_int= 0x3f3f3f3f;
void read(){};
template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar)
{
    x= 0;
    char c= getchar();
    bool flag= 0;
    while (c < '0' || c > '9')
        flag|= (c == '-'), c= getchar();
    while (c >= '0' && c <= '9')
        x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();
    if (flag)
        x= -x;
    read(Ar...);
}
template <typename T> inline void write(T x)
{
    if (x < 0) {
        x= ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#else
    startTime = clock ();
    freopen("data.in", "r", stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#else
    endTime= clock();
    printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn=2e5+9;
int a[maxn];
int nxt[maxn];
int id[maxn];
vector<PII>x,y;
int main()
{
    //rd_test();
	int n;
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		id[i]=n+1;
	}
	for(int i=n;i>=1;i--){
		nxt[i]=id[a[i]];
		id[a[i]]=i;
	}
	x.push_back({0,n+1});
	y.push_back({0,n+1});
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==x.back().first&&a[i]==y.back().first){
			x.push_back({a[i],nxt[i]});
		}
		else if(a[i]==x.back().first){
			y.push_back({a[i],nxt[i]});
			ans++;
		}
		else if(a[i]==y.back().first){
			x.push_back({a[i],nxt[i]});
			ans++;
		}
		else 
		{
			ans++;
			if(x.back().second>y.back().second){
				y.push_back({a[i],nxt[i]});
			}
			else 
				x.push_back({a[i],nxt[i]});
		}
	}
	cout<<ans<<endl;
    //Time_test();
}

D2

#include <bits/stdc++.h>
#include <unordered_map>
#define debug(a, b) printf("%s = %d\n", a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll= 1e18;
const int INF_int= 0x3f3f3f3f;
void read(){};
template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar)
{
    x= 0;
    char c= getchar();
    bool flag= 0;
    while (c < '0' || c > '9')
        flag|= (c == '-'), c= getchar();
    while (c >= '0' && c <= '9')
        x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();
    if (flag)
        x= -x;
    read(Ar...);
}
template <typename T> inline void write(T x)
{
    if (x < 0) {
        x= ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#else
    startTime = clock ();
    freopen("data.in", "r", stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#else
    endTime= clock();
    printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn=2e5+9;
int a[maxn];
int nxt[maxn];
int id[maxn];
vector<PII>x,y;
int main()
{
    //rd_test();
	int n;
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		id[i]=n+1;
	}
	for(int i=n;i>=1;i--){
		nxt[i]=id[a[i]];
		id[a[i]]=i;
	}
	x.push_back({0,n+1});
	y.push_back({0,n+1});
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==x.back().first&&a[i]==y.back().first){
			x.push_back({a[i],nxt[i]});
		}
		else if(a[i]==x.back().first){
			x.push_back({a[i],nxt[i]});
		}
		else if(a[i]==y.back().first){
			y.push_back({a[i],nxt[i]});
		}
		else 
		{
			ans++;
			if(x.back().second>y.back().second){
				x.push_back({a[i],nxt[i]});
			}
			else 
				y.push_back({a[i],nxt[i]});
		}
	}
	cout<<ans<<endl;
    //Time_test();
}