Codeforces Round#768(Div.2) E. Paint the Middle

Codeforces Round#768(Div.2) E. Paint the Middle 题意：

给定编号从 1 到 n的 n 个元素，元素 i 具有值 ai 和颜色 ci，最初,对于所有 i，ci=0。
可以应用以下 *** 作:
选取三个元素i、j、k（1≤i 问 m a x ∑ c i maxsum ci max∑ci为多少

题解：

可以将这题看成区间覆盖的问题，只要两头有个相同的数显然可以将中间所有的ci变为1.所以我们只需要预处理所有的数出现最后一次的位置，然后判断当前的i是否在这个以a[i]为左端点的区间内，如果是则答案数+1，反之贪心的选择一个最右的端点;

#include
using namespace std;
int a[200005], ed[200005];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		ed[a[i]] = i;
	}
	int cover = 0,r=0,res=0;
	for (int i = 1; i <= n; i++)
	{
		r = max(r, ed[a[i]]);
		if (cover > i)res++;
		else cover = r;
	}
	cout << res << endl;
}