题解：AT_abc381_d [ABC381D] 1122 Substring

zhouruoheng · 2024-11-23 13:06:47 · 题解

将数组 a 变成元素加个数的形式，元素数组为 b，个数为 c，如 \mathtt{1,1,2,2,3,3,3}，b 就是 \mathtt{1,2,3}，c 就是 {2,2,3}。用双指针来做。用 v 统计是否出现，j 表示左指针，i 表示右指针。统计答案就是 i-j+1。

• 当 c_i=1 时，说明 i 不能贡献，直接将 j 移动到 i+1。
• 当 c_i>2 时，i 只能作为开头或结尾，若 b_i 没出现过，统计一次答案。然后将 j 移动到 i，标记 b_i 出现。
• 当 c_i=2 时，若 b_i 出现过，则一直移动 j 直到 v_{b_i}=0。然后标记 b_i 出现。

移动 j 时要将 v_{b_j} 变为 0。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N],b[N],c[N];
int v[N];
void solve()
{
    cin>>n;
    int tot=0;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]!=a[i-1]) b[++tot]=a[i],c[tot]=1;
        else c[tot]++;
    }
    int j=1,ans=0;
    for(int i=1;i<=tot;i++)
    {
        if(c[i]<2) while(j<=i) v[b[j++]]=0;
        else if(c[i]>2) 
        {
            if(!v[b[i]]) ans=max(ans,(i-j+1)*2);
            while(j<i) v[b[j++]]=0;
            v[b[i]]=1;
        }
        else 
        {
            while(j<=i&&v[b[i]]) v[b[j++]]=0;
            v[b[i]]=1;
        }
        if(j<=i) ans=max(ans,(i-j+1)*2);
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}