7-2 乒乓人训练大师（双指针）

在一片古老的大陆上，生活着一群乒乓人。作为一个古老的种族，乒乓人的族群中保存着 m 种不同的种族天赋。传说在上古时期，存在着兼具所有种族天赋的超级乒乓人：他们具有着御气飞行、移山填海的强大能力。然而，在漫长的时间中，超级乒乓人的能力渐渐被分化、稀释。如今，每一个现存的乒乓人最多只具有一种种族天赋。

小 M 是一名乒乓人训练大师，她的目标是让超级乒乓人重见天日。为了达成这个目标，她对 n 名乒乓人展开了训练，其中第 i 名乒乓人初始的种族天赋为 ai​。在训练时，这些乒乓人按照编号 1 到 n 的顺序站成一排。接着，小 M 会对他们使用赋值天赋的能力。具体来说，每次使用能力的时候，小 M 都可以指定两名相邻的乒乓人 (i,j)(∣i−j∣=1)，并将第 i 名乒乓人具有的全部天赋复制给第 j 名乒乓人。（注意：第 i 名乒乓人的天赋并不会发生变化）

小 M 的目标是让所有的 n 名乒乓人都成为超级乒乓人，即对于任意的 i∈{1,…,n},j∈{1,…,m}，第 i 名乒乓人都具有种族天赋 j。现在，小 M 想让你帮忙计算，她最少发动多少次能力才能达成这个目标。

输入格式:

第一行输入两个整数 n,m(2≤n≤3×105,2≤m≤3×105)，表示乒乓人数量和种族天赋的数量。

第二行输入 n 个空格隔开的整数 a1​,…,an​(1≤ai​≤m)，其中 ai​ 表示第 i 名乒乓人初始时具有的种族天赋。

输入保证每一个种族天赋都会出现，即 ∀j∈{1,…,m},∃i∈{1,…,n},ai​=j。

输出格式:

输出一行一个整数，表示小 M 最少需要发动多少次能力。

输入样例1:

4 2
1 2 1 2

输出样例1:

4

输入样例2:

10 5
1 4 2 5 3 2 3 5 1 2

输出样例2:

13

代码长度限制

100 KB

时间限制

2000 ms

内存限制

512 MB

#include <bits/stdc++.h>
typedef long long ll;
typedef double db;
using namespace std;
const int N = 3e5 + 10;
int a[N],n,m;
int c[N],cnt;
signed main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }

    int res = INT_MAX;
    for(int l=1,i=1; i<=n; i++)
    {
        if(++c[a[i]] == 1) cnt ++ ;
        while(l <= i && cnt == m)
        {
            res = min(res,i - l + 1);
            // cout << i << " " << l << endl;
            if(--c[a[l]] == 0) cnt -- ;
            l ++ ;
        }
    }

    cout << res + n - 2 << endl;

    return 0;
}