博客园：
https://www.cnblogs.com/AK-ls/p/15202863.html
以下为博客园粘贴：

emmmmmm， 这是在那场比赛中唯一没有A掉的题目， 首先应该想到， 两个相同数字之间最后的值一定是相同的， 所以我们把该序列分成若干个区间， 每个区间的值最终相同， 这个还是挺容易实现的， 我们可以记录每个值的右端点， 我们可以把该序列从左向右扫描， 每次都取最大的右端点， 当扫描的数与右端点重合是， 这个区间就完成了， 假如这个区间的种类数是num， 那先把他们变成一样的数的代价就是num-1， 这个就可以先统计到答案中， 这样我们得到n个区间， 每个区间都能取一定的值， 且这些值互不相同。 当时在赛场上想的就是， 都取最小值， 然后求一个最长上升子序列（假设长度为l）再把答案加上n-l就是结果， 当时时间紧迫， 最后也没有调出来， 但这个思路显然不对， 前面的数要尽可能小， 后面的数要尽可能大， 后来就有点卡住了。 再后来， 我问了银牌爷zyz， 得出了方案， 用f[i]表示当前前i个区间所能构成的最长上升子序列， 在把所有的取值从小到大排序， 每取出一个值， 获得它的区间标号pos， 那么f[pos] = max(f[pos], max(f[1...pos-1]) + 1);至于前i个f[i]的最大值， 可以用树状数组或者线段树维护， 把数从小到大扫描也就能够统计所有可行的方案， 那么这个问题就解决了
（PS： 1.线段树被卡， 疑惑？？？？ 2.在TLE多次之后， 得出一个结论， 尽量不要在循环中写memset， 否则在特殊数据中， 复杂度会变成

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 10;
const int MAXM = 2e3 + 10;
const int mod = 1e6 + 7;
const double eps = 1e-6; 

template < typename T > inline void read(T &x) {
    x = 0; T ff = 1, ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') ff = -1;
        ch = getchar(); 
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar(); 
    }
    x *= ff; 
}

int n, b[MAXN], a[MAXN], vis[MAXN], num[MAXN * 10];
int m[MAXN * 10]; 
vector < pair < int, int > > v; 
int top = 1, ans1 = 0, ans2 = 0;

inline int query(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans = max(ans, a[x]);
    return ans;
}

inline void change(int x, int y) {
    for (; x <= n; x += x & -x) a[x] = max(a[x], y);
    return;
}

int main() { 
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        int x = Hash(a[i]);
        m[x] = i;
    }
    int l = 1, r = 0, cnt = 0, mi = INF;
    for (int i = 1; i <= n; ++i) {
        int u = Hash(a[i]);
        r = max(r, m[u]);
        mi = min(mi, a[i]);
        if (!vis[u]) {
            vis[u] = true;
            v.push_back({a[i], top});
            ++cnt;
        }
        if (r == i) {
            ans1 += cnt - 1;
            l = r = i + 1;
            cnt = 0;
            mi = INF;
            ++top;
//            memset(vis, false, sizeof(vis)); 
        }
    }
    --top;
    sort(v.begin(), v.end());
    n = v.size();
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; ++i) {
        int x = v[i].second;
        int v = query(x - 1);
        if (a[x] < v + 1) {
            a[x] = v + 1;
            ans2 = max(ans2, v + 1);
            change(x, v + 1);
        }
    }
    printf("%d", ans1 - ans2 + top);
    return 0;
}