Secuencias Continuas (OMI 2013, Día 2, Prob 4) resuelto con Pivoteo en O(N lg N) esperado. Funciona porque una pareja de contiguos contiene al menor en un intervalo o esta a la izquierda o a la derecha. Y si contiene al menor, entonces contiene desde el menor hasta algún numero mayor a este como uno de los intervalos contiguos, y como son N oper…

SecContPivoteo.cpp

#include<iostream>
#include<fstream>
using namespace std;
const int MAXN=50005;
int S[MAXN],I[MAXN],loga[MAXN];//loga[k] es el piso del logaritmo de k
int Tm[MAXN][17];
int TM[MAXN][17];

inline int maxim(int a,int b){ //Maximo del [a,b] O(1)
    if(a==b) return TM[a][0];
    int t=loga[b-a+1];
    return max(TM[a][t],TM[b-(1<<t)+1][t]);
}

inline int minim(int a,int b){//Minimo del [a,b] O(1)
    if(a==b) return Tm[a][0];
    int t=loga[b-a+1];
    return min(Tm[a][t],Tm[b-(1<<t)+1][t]);
}

inline bool valid(int q,int p,int a,int b){ //Checa si el intervalo [a,b] es contiguo en O(1)
    if(p<q||a>b||p>b||q<a) return false;
    return (maxim(q,p)-minim(q,p))==(p-q);
}

int resolv(int a,int b){//Resuelvo para el intervalo [a,b]
    if(b-a<1) return 0;
    if(b-a==1) return 1;
    int q,maxi,L,R,d,T=maxim(a,b),s,p,r=I[minim(a,b)];//Pivoteo con el menor´(r)
    L=resolv(a,r-1);//Recursividad FTW!
    R=resolv(r+1,b);
    maxi=max(L,R);
    p=q=r;
    for(int i=S[r];i<=T;i++){//Voy checando el menor intervalo que contiene del S[r] al i 
        s=I[i];
        p=max(p,s);
        q=min(q,s);
        if(q>b||q<a) continue;
        d=p-q;
        if(valid(q,p,a,b)&&(valid(p+1,p+1+d,a,b)||valid(q-1-d,q-1,a,b))){//Checo si puede ser parte de una pareja de contiguos
            maxi=max(maxi,d+1);
        }
    }
    return maxi;
}

int main(){
    int N,u=-1,t=1;
    //freopen("hugodos24.in","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        if(i==t){
            u++;
            t*=2;
        }
        loga[i+1]=u;//Precalculo loga
        scanf("%d",&S[i]);
        S[i]--;
        TM[i][0]=Tm[i][0]=S[i];
    }
    u=loga[N]+1;
    for(int k=1;k<u;k++){ //Precalculo del RMQ
        for(int i=0;i<N;i++) {
            Tm[i][k]=min(Tm[i][k-1],Tm[min(N-1,i+(1<<(k-1)))][k-1]);
            TM[i][k]=max(TM[i][k-1],TM[min(N-1,i+(1<<(k-1)))][k-1]);
        }
    }
    for(int i=0;i<N;i++){ //Calcular en qué posición esta el numero i
        I[S[i]]=i;
    }
    printf("%d",2*resolv(0,N-1));
}