小红的aba子序列（离散化、二分、dp维护区间最短）

TP

思路：

• 显然每种数离散化一下，记录下对应出现的坐标。
• 枚举每一种数，排除前 k 个和后 k 个后，中间的区间就是需要查找的是否有可能满足情况。
• 直接维护是很困难的，这题用了二分的方法，二分 k 的值，对于每种 k check 一下每种数上面说的那个区间是否有解。

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#define debug cout << "debug--- "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 1e5 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int a[N];
vector<int> vec[N];
int f1[N], f2[N], id[N];
//f[i] 意为第 i 位最早的 j，满足 区间 [i,j] 有 k 个值相同的数
//预处理最小、次小的 f1[i],f2[i]，满足最小、次小的 k 个值相同的数 值不同
// 
//id[i] 记录 f1[i] 的 k 个值相同的数 值是多少

bool check(int mid) {
    
    for (int i = 1; i <= n; i++)f1[i] = f2[i] = id[i] = INF;

    //对于每一种数，找到长度为 mid 的区间维护
    for (int i = 1; i <= m; i++) {
    
        int siz = vec[i].size();

        for (int j = mid - 1; j < siz; j++) {
    
            int be = vec[i][j - mid + 1];
            int ed = vec[i][j];

            f1[be] = ed, id[be] = i;
            //因为某位只能存在一种数，所以只有f1

            /* if (f1[be] > ed) { f2[be] = f1[be], f1[be] = ed; id[be] = i; } else if (f2[be] > ed)f2[be] = ed;*/
        }
    }

    //反向 dp，每一位维护右边最早能形成 k 个数的 位置
    for (int i = n - 1; i >= 1; i--) {
     
        //能更新最小，则次小获得最小，更新最小
        if (f1[i] > f1[i + 1]) {
    
            if (id[i] != id[i + 1])f2[i] = f1[i];
            f1[i] = f1[i + 1], id[i] = id[i + 1];
        }
        //否则，当且仅当数类型不同才更新最小
        else if (f2[i] > f1[i + 1] && id[i] != id[i + 1])f2[i] = f1[i + 1];
        if (f2[i] > f2[i + 1])f2[i] = f2[i + 1];
        //次小随意更新
    }

    for (int i = 1; i <= m; i++) {
    
        int siz = sz(vec[i]);

        //最后对于每种数，找到累计 k 个的最左端和最右端

        if (siz >= mid + mid) {
    
            int l = vec[i][mid - 1], r = vec[i][siz - mid];

            //判断是否有 中间的的 k 个数为 b，且a ≠ b 
            if (f1[l] < r && id[l] != i || f2[l] < r)return true;
        }
    }
    return false;
}

void solve() {
    
    cin >> n;
    m = 0;
    map<int, int> mp;//离散化
    forr(i, 1, n) {
    
        cin >> a[i];
        if (!mp.count(a[i]))mp[a[i]] = ++m;
        a[i] = mp[a[i]];
        vec[a[i]].push_back(i);
    }

    int l = 1, r = n / 3;

    while (l < r)
    {
    
        int mid = l + r + 1 >> 1;
        if (check(mid))l = mid;
        else r = mid - 1;
    }

    //最后一定还要check一下，有可能无解
    if (!check(l))cout << -1;
    else cout << n - l * 3;
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
    
        solve();
    }
    return 0;
}
/* */