Alex and Complicated Task

Soru Metni

Size tam sayılardan oluşan bir dizi verilecektir a1, a2, ..., an. En uzun b1, b2, ..., b4m dizisini bulmalısını ve aşağıda verilen şartları sağlamalıdır:

• b4k + 1 = b4k + 3 her k için;
• b4k + 2 = b4k + 4 her k için;
• b dizisi a dizisinin bir alt dizisidir(ardışık olmasına gerek yok).

Sizden istenen size a dizisi verildiğinde maximum 4m değerini ve b dizini yazdırmanız.

Input

İlk satırda tek bir tam sayı n (1 ≤ n ≤ 5·105). İkinci satırda  a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

İlk satırda tek bir tam sayı 4m - istenilen dizi b'nin mümkün olan en uzun uzunluğu. İkinci satırda 4m tane tam sayı b1, b2, ..., b4m. Birden fazla çözüm varsa herhangi birini yazdırmanız yeterlidir.

Sample test(s)

input

4
3 5 3 5

output

4
3 5 3 5

input

10
35 1 2 1 2 35 100 200 100 200

output

8
1 2 1 2 100 200 100 200

--------------------------------------------------------------------------------------------------------------------------
Soru Linki:http://codeforces.com/contest/467/problem/E
--------------------------------------------------------------------------------------------------------------------------
Çözüm Metni

Sorunun çözümü greedy dir. Ancak hesaplamayı yapabilmek için segment tree data structure'ını kullanmak gerekmektedir. Aynı zamanda bu soruda kullanılacak olan segment tree veri yapısı 2014 yaz kampında anlatılmıştır kamptaki yeni öğrenen öğrenciler de gayet rahat çözebilir.

Soru da bahsedildiği üzere M tane 4 lük grup seçmemiz gerekmektedir. Seçeceğimi her bir grup abab formatında olmalıdır yani 1. ve 3. sayı ile 2. ve 4. sayı aynı olmalıdır. Yapmamız gereken temel şey şudur: seçebileceğimiz abab formatında olan ve son indisi en küçük olan ilk grubu seçmek ardından yine xyxy formatında olan ve ilk grupla kesişmeyen son indisi en küçük olan ilk grubu seçmek ve bu şekilde devam edecektir. Bu çözüm neden çalışır?

İspat: Aslında gayet anlaşılır ama biz yine de ispatlayalım. Varsayalım ki abab formatında olan ve son indisi i olan bir grup ilk grup olduğunda en iyi çözüm geliyor olsun ancak yine xyxy formatında olan ve son indisi j olan bir grup ilk grup olduğunda en iyi çözüm gelmiyor olsun aynı zamanda i>j olsun. Bu durum aslında çelişkidir çünkü ikinci seçilecek grubun ilk indisi daima i ve j den büyük olmalıdır bu demek oluyor ki i den büyük olan j den de büyük olacaktır yani abab formatında olandan gelecek olan çözüm aslında xyxy formatında olandan gelcek olandan büyük ya da ona eşittir.

Peki bu çözümü nasıl kodlarız?
1 den N e doğru giderken i. indiste iken i. indisi bir kesim noktası olarak kabul edebilir miyiz buna bakmalıyız. Kesim noktası şimdiye kadar gelmiş grupları kesmeden yeni bir grup oluşturulabiliyor mu sorgusuna pozitif cevap veren noktalardır. Örneğin 12123434, son 4 ün bulunduğu nokta bir kesim noktasıdır ancak 12132434 burada son 4 ün bulunduğu nokta bir kesim noktası değildir.

Peki kesim noktası olup olmadığını nasıl sorgulayabiliriz?
i. indiste iken A[i]=A[j] ve j<i olan en büyük j değerini bulduğumuzda eğer son kesim noktası ile j arasında(son kesim noktası ve j dahil değil) kendisiyle aynı değere sahip bir sonraki sayı j ile i arasında olan bir sayı varsa i yeni bir kesim noktasıdır. Şekille açıklamak gerekirse

--------|-----------|-----|-----|-----|-----|-----|--------
    son kesim     a      a'     b      j      b'     i

A[j]=A[i] olsun ve A[a]=A[a'] olsun ve A[b]=A[b'] olsun. Bu durumda i bir kesim noktasidir. a ve a' indislerindeki sayilar onun kesim noktasi olmasina imkan tanimazken b ve b' noktalarindaki sayilar buna imkan tanimaktadir.

Son kesim noktasi ile j arasindaki uygun sayilarin var olup olmadigi nasil bulunur?

Eger ki 1 den N e kadar gezerken i. indiste iken A[i]=A[j] ve j<i olan en buyuk j degerinin segment tree deki degerini i ile guncellersek ve herhangi baska bir i indisinde iken son kesim noktasi ve j arasindaki max degeri sorguladigimizda bu deger j ile i arasinda ise (j den buyuk olmasi yeterlidir cunku adim adim geldigimiz icin simdiye kadar butun update edilen degerler i den kucuktur) aranan noktalardan en az bir tane var demektir.

Tabiki siz ciktiyi dogru yazdirabilmek icin farkli veriler tutumaniz gerekecektir.

--------------------------------------------------------------------------------------------------------------------------

Çözüm Kodu (Kod için Emin Ayar'a teşekkürler)

#include <bits/stdc++.h>

#define fi first
#define se second
#define o ((b+e)/2)

using namespace std;

typedef pair <int,int> ii;
int N,ar[510000],as[510000],prev[510000],tt[510000];
ii say[510000],seg[500000*5];
vector <int> res;

int comp( const int &a , const int &b ){ return ar[a] < ar[b]; }

ii upd( int k , int b , int e , int a , int t ){
if( b > a || e < a ) return seg[k];
if( b == e ) return seg[k]=ii(t,b);
return seg[k]=max( upd( 2*k , b , o , a , t ) , upd( 2*k+1 , o+1 , e , a , t ) );
}

ii find( int k , int b , int e , int a1 , int a2 ){
if( b > a2 || e < a1 ) return ii(0,0);
if( a1 <= b && e <= a2 ) return seg[k];
return max( find( 2*k , b , o , a1 , a2 ) , find( 2*k+1 , o+1 , e , a1 , a2 ) ); 
}

int main(){

cin >> N;

for( int i=1 ; i<=N ; i++ ) scanf(" %d",&ar[i]),as[i]=i;
sort( as+1 , as+1+N , comp );
for( int i=1,tut=-1,cnt=0 ; i<=N ; i++ ){
if( ar[as[i]] != tut ) cnt++,tut=ar[as[i]];
tt[cnt]=ar[as[i]];
ar[as[i]]=cnt;
}
memset( as , 0 , sizeof as );
for( int i=1 ; i<=N ; i++ ){
prev[i]=as[ar[i]];
as[ar[i]]=i;
}

int size=0,lastcut=1;
for( int i=1 ; i<=N ; i++ ){
if( say[ar[i]].se != size ) say[ar[i]]=ii(0,size);
say[ar[i]].fi++;
if( say[ar[i]].fi == 4 ){
size++;
res.push_back( tt[ar[i]] );
res.push_back( tt[ar[i]] );
res.push_back( tt[ar[i]] );
res.push_back( tt[ar[i]] );
lastcut=i+1;
continue;
}
upd( 1 , 1 , N , prev[i] , i );
if( prev[i]-1 < lastcut ) continue;
ii q=find( 1 , 1 , N , lastcut , prev[i]-1 );
if( q.fi > prev[i] ){
size++;
res.push_back( tt[ar[q.se]] );
res.push_back( tt[ar[i]] );
res.push_back( tt[ar[q.se]] );
res.push_back( tt[ar[i]] );
lastcut=i+1;
continue;
}
}

cout << size*4 << endl;
for( int i=0 ; i<(int)res.size() ; i++ ) printf("%d ",res[i]);

return 0;

}