主播主播嘟到ds维护dp题咋办？没事我们有并查集贪心！

· · 题解

这道题的树状数组和 dp 做法实在是太不牛了。我们有除了离散化外为 O(N\alpha(N)) 的贪心做法。

首先给出一个直觉贪心碰到更早的能使用的四元组 \{x,y,x,y\} 就直接使用。因为当前四元组不会影响下一组，所以这个是对的。

接着我们考虑怎么继续贪。
首先碰到某种元素的第一个就记录下来。
后面再碰到相同元素，我们发现，他们和中间的元素可以形成 \{x,y,x\} 的结构。这样子的结构可以留下来匹配后面的 y。所以我们记录下来。
此时我们称这样子的 y 为可用的，后面一出现我们就直接记录答案。

如果暴力枚举两个数之间的位置，应当是 O(N)。于是我们的复杂度来到了惊人的 \Theta(N^2)。
但是注意到，一个数字作为 y 被多个 \{x,....x\} 的结构包含时，只有最早结束的那个结构会对后续转移有效。因此我们用一个并查集维护每个位置后面下一个没有被使用过的位置。
而一个位置的元素变得可用时，在并查集中将其位置连向下一个位置即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define gc getchar
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=5e5+5;
int fa[N],n,a[N],b[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int ans[N],ps[N],ff[N],tp1,tp2,tp3;
int fst[N],f[N];
void clear(){
    for(int i=1;i<=tp2;i++)f[ps[i]]=0;
    for(int i=1;i<=tp3;i++)fst[ff[i]]=0;
    tp2=tp3=0;
}
void init(){
    for(int i=1;i<=n;i++)b[i]=a[i];
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b,fa[i]=i;
    fa[n+1]=n+1;
}
void solve(){
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    init();
    for(int i=1;i<=n;i++){
        if(f[a[i]]){
            ans[++tp1]=b[f[a[i]]],ans[++tp1]=b[a[i]];
            ans[++tp1]=b[f[a[i]]],ans[++tp1]=b[a[i]];
            clear();
        }else if(fst[a[i]]){
            for(int j=fst[a[i]]+1;j<i;j++){
                j=find(j);if(j>=i)break;
                fa[j]=find(j+1);
                if(!f[a[j]])f[a[j]]=a[i],ps[++tp2]=a[j];
            }
        }else fst[a[i]]=i,ff[++tp3]=a[i];
    }
    cout<<tp1<<'\n';
    for(int i=1;i<=tp1;i++)cout<<ans[i]<<' ';
}
signed main(){ios;solve();}

P.S. 粘个快读板子就是最优解了。