Codeforces Round 267 Div. 2 Problem E - Alex and Complicated Task

Problem Statement:
467E - Alex and Complicated Task

Solution:
We maintain an array P and a set S, and we consider the elements from left to right:
1. If \(v = a_i\) is not in S yet, add it in and note its index. Hence S will store the index j of the first occurrence of the number \(v\).
2. Else, we set P[i] to index of j of \(v = a_i\) we stored in S.
3. If between P[i] and i there exist P[j] that is less than P[i], then the element P[j], P[i], j, and i forms one desired sequence! Store them and reset S.



To speed up the searching minimum P[j] in between P[i] and i, we use a segment tree, as follows:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <utility>
using namespace std;

int N;
map<int, pair<int,int> > S;
int segtree[2000003];
int mark[500003];
int cnt[500003];
int a[500003];
vector<int> st;

void build(int p, int L, int R){
    if(L==R){
        segtree[p] = mark[L];
        return;
    }
    int M = (L+R)/2;
    build(2*p, L, M);
    build(2*p+1, M+1, R);
    segtree[p] = min(segtree[p], segtree[2*p]);
}

int rmq(int p, int L, int R, int S, int T){
    if(R < S || T < L) return -1;
    if(S <= L && R <= T){
        return segtree[p];
    }
    int M = (L+R)/2;
    int left = rmq(2*p, L, M, S, T);
    int right = rmq(2*p+1, M+1, R, S, T);
    if(left < 0) return right;
    if(right < 0) return left;
    return min(left, right);
}

int update(int p, int L, int R, int S, int T){
    if(R < S || T < L) return rmq(p, L, R, L, R);
    if(S <= L && R <= T){
        segtree[p] = mark[L];
        return segtree[p];
    }
    int M = (L+R)/2;
    int left = update(2*p, L, M, S, T);
    int right = update(2*p+1, M+1, R, S, T);
    return (segtree[p] = min(left, right));
}

int main(){
    scanf("%d", &N);
    int u, v;
    int ans = 0;
    for(int i=0;i<N;++i)mark[i] = i;
    build(1, 0, N-1);
    for(int i=0;i<N;++i){
        scanf("%d", &u);
        a[i] = u;
        if(S.find(u) != S.end()){
            if(S[u].second == -1){
                S[u].second = i;
                mark[S[u].second] = S[u].first;
                update(1, 0, N-1, S[u].second, S[u].second);
            } else {
                S[u].second = i;
                mark[i] = S[u].first;
                update(1, 0, N-1, i, i);
            }
            cnt[S[u].first]++;
            if ((v = rmq(1, 0, N-1, S[u].first, S[u].second)) < S[u].first){
                ++ans;
                st.push_back(u);
                st.push_back(a[v]);
                S.clear();
            } else if(cnt[S[u].first] == 3){
                st.push_back(u);
                st.push_back(u);
                ++ans;
                S.clear();
            }
        } else {
            S[u] = make_pair(i, -1);
            update(1,0,N-1,i,i);
        }
    }
    printf("%d\n", ans*4);
    if(ans == 0) return 0;
    for(int i=0;i<ans;++i){
        if(i!=0)printf(" ");
        printf("%d %d %d %d", st[2*i+1], st[2*i], st[2*i+1], st[2*i]);
    }
    printf("\n");
    return 0;
}