[CF 467E] Alex and Complicated Task

作法：

首先想法是 greedy ，我們只要找到一個最小的$i$，使得$a[1],...,a[i]$中存在一個長度為$4$的子序列，滿足他形如$x,y,x,y$即可。當找到這個$i$之後顯然最好的方法就是取那$4$個數，然後把一切清空，當成原數列只有$a[i+1],...,a[n]$去作就可以了。因此問題變為要如何決定那樣子的最小的$i$。

考慮從$1$開始往右掃描，當遇到一個數是之前出現過的數時，假設此時掃描到$a[x]$，並且前一個出現過同樣數字的位子為$a[y]$，那麼我們可以把$a[x],a[y]$之間的所有數字當標記上$a[x]$（注意不是標記位置，是標記數值），因為之後只要一遇到$a[x],a[y]$中間的任何一個數，我們就找到所求的序列了。而為了避免重複標記相同位置的數，可以用一個 stack 來維護，每次加入新數字時，如果這個數字已經在 stack 裡出現過了，那麼就不斷 pop 直到遇到那個數為止，並且把中間 pop 掉的數都標記上當前的數的值。而只要當前遇到的數字是已被標記過的，那麼就等於找到所求的最小$i$了，把那$4$個數丟進答案裡並把所有資料結構清空即可。另外還要注意到也有可能四個數相同，而這只要再多用一個 map 紀錄一個數字出現了幾次就可以了，當一有某個數字出現$4$次時也等於找到一組解了。

code :

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int maxn=500000+10 ;
 
int a[maxn],st[maxn],sz ;
set<int> ins ;
map<int,int> mp,mp0 ;
vector<int> ans ;
inline void init()
{
    sz=0 ; ins.clear() ;
    mp.clear() ; mp0.clear() ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=n;i++)
    {
        if(++mp0[a[i]]==4)
        {
            for(int j=0;j<4;j++) ans.push_back(a[i]) ;
            init() ; continue ;
        }
        auto it=mp.find(a[i]) ;
        if(it!=mp.end())
        {
            for(int j=0;j<2;j++)
                ans.push_back(it->S) ,
                ans.push_back(it->F) ;
            init() ; continue ;
        }
        if(!ins.count(a[i]))
            st[sz++]=a[i] , ins.insert(a[i]) ;
        else
        {
            while(st[sz-1]!=a[i])
                ins.erase(st[sz-1]) ,
                mp[st[sz-1]]=a[i] ,
                sz-- ;
        }
    }
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ');
}