题解：CF1630C Paint the Middle

· · 题解

爆标了！？

注：做法由 CRl_b 神犇提供。

显然题目相当于区间染色，那么如果能找到一个极大的区间，直接把区间内的所有数染色即可，而且显然对于一个数 v，染色区间直接取到 v 最后一次出现位置是绝对不劣的，所以预处理出每个数最后一次出现次数，问题是是否存在区间内有些数不染色的情况？

这意味着没被染色的数要作为另外染色区间的端点，把玩一下发现是可能的，如图所示：

此时两个区间存在重叠，显然先把 (1, 3) 与 (3, 6) 的数染色，再以 3 和 8 为端点将 (3, 8) 染色更优（注意此处指的是下标）。

也就是说，对于一个已经找到的染色区间，若存在另一个区间与其重叠并在其右边（因为从左边扫的话不用管左边），那么遵上述即可得到更优的染色结果就，因为这相当于从原本的区间内延伸一段染色区间，必然会更优。

所以只需要顺序枚举每个下标 i 作为区间起点，记颜色 c 的最后一次出现下标为 lst_c，则只需要找出 \max \limits _ {j \in (i, lst_{a_i}) \land lst_{a_j} > lst_{a_i}} lst_{a_j} 并将区间 (i, lst_{a_i}) 与 (j, lst_{a_j}) 合并即可，即找出重叠并延伸最长的区间。

于是乎你得到了 \mathcal O(n) 做法！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, a[N], lst[N], ans;bool c[N];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], lst[a[i]] = i;
    for (int i = 1; i <= n; i ++)
        if (!c[i]){int fst = 0;
            for (int j = i + 1; j < lst[a[i]]; j ++)
                if (lst[a[j]] > lst[a[i]])
                    fst = max(fst, lst[a[j]]);
            for (int j = i + 1; j < lst[a[i]]; j ++)
                if (lst[a[j]] != fst)
                    ans += !c[j], c[j] = 1;
        }
    return cout << ans, 0;
}