SPOJ - Trapezoid

Blog ini udah berdebu parah ya ._. Well mau diapa juga, sudah mendekati ujian nasional, dan bio-kim-bindo saya masih menyedihkan :s Sebenarnya saya ingin ngeblog tentang Pelatnas 2 yang sudah saya lalui, tapi karena membahas soal ini lebih pendek nulisnya, saya mau nulis ini dulu :P

Soal bisa diakses di SPOJ - TRAPEZBO
Omong-omong, ini merupakan salah satu soal latihan pas Pelatnas 2 yang waktu itu belum saya AC - kan, baru beberapa hari yang lalu saya berhasil menyelesaikannya.

Untuk mempermudah persoalan, soal ini bisa diubah perintahnya menjadi : "Tentukan LIS dari trapezoid masukan, dan cari ada berapa cara bisa mendapatkan LIS itu!", di mana untuk tiap 2 trapezoid tidak boleh ada yang intersect. Bagaimana syarat 2 trapezoid tidak intersect? misal trapezoid A berada di kiri trapezoid B dan mereka tidak intersect, jelas bahwa harus berlaku :

kanan-bawah A < kiri-bawah B dan
kanan-atas A < kiri-atas B

Pada saat Pelatnas, solusi yang bisa saya dapatkan adalah O(N log ^ 2 N). Pada solusi ini, saya sort dulu trapezoid berdasarkan kiri-bawah. LIS yang berujung di indeks yang sekarang diproses bisa diperoleh dengan meng-query berdasarkan koordinat kiri-bawah dan kiri-atas. Setelah didapat LIS yang berujung di situ, lakukan update pada range tree berdasarkan kanan-bawah dan kanan-atas.

Apakah solusi tersebut AC? Tidak! Bahkan setelah saya ubah dari range tree yang berbentuk segment tree + segment tree menjadi BIT + BIT, ternyata hasilnya tetap TLE. Setelah itu, karena penasaran saya googling, dan dikatakan bahwa solusi yang diharapkan adalah O(N log N). Akan tetapi, saya tidak mengerti jadi saya lupakan dulu.

Beberapa hari yang lalu saya kembali ke soal ini. Saya berpikir bagaimana cara menghilangkan satu dimensi pada strukdatnya. Untuk mempermudah, saya berpikir cara menghilangkan dimensi "bawah". Karena iseng, saya berpikir bagaimana jika saya sort berdasarkan kanan-bawahnya? Karena saya "sweep" dari kiri ke kanan, maka pada saat memproses bagian kanan trapezoid, tentu akan dilakukan update. Sedangkan untuk melakukan update saya perlu mengetahui panjang LIS yang berujung pada trapezoid itu. Lalu di mana saya harus melakukan query?

Solusinya ternyata simple : Buat array trapezoid lagi, namun sort berdasarkan kiri-bawahnya! Perhatikan sebelum kita melakukan update dengan koordinat kanan-bawah berupa x, semua trapezoid yang koordinat kiri-bawahnya <= x harus sudah di-query. Kemudian, karena koordinat kiri-bawah trapezoid pasti < koordinat kanan-bawah nya, maka pasti ketika kita akan melakukan update berdasar suatu trapezoid, kita sudah mendapatkan LIS yang berujung pada trapezoid itu!

Dengan cara tersebut, kita berhasil menghilangkan satu dimensi pada strukdat, yaitu bawah, sehingga mengerjakannya bisa dalam O(N log N). Oiya, walaupun belum saya sebut, jelas bahwa ada koordinat yang harus dikompres. Menurut saya, soal ini salah satu contoh baik bahwa solusi optimal untuk suatu soal bisa jadi lebih simple dari non-optimalnya (range tree itu capek bikinnya)

Berikut implementasi saya :
 

#include <cstdio>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define mp make_pair

typedef pair<int,int> pii;

const int MOD = 30013;
const int N = 100005;

struct Trapezoid{
    int aki;
    int bki;
    int aka;
    int bka;
    int id;
};

bool ByKa(Trapezoid a,Trapezoid b){
    return a.bka < b.bka;
}

bool ByKi(Trapezoid a,Trapezoid b){
    return a.bki < b.bki;
}

void Add(pii &x,pii &y){
    if(x.fi < y.fi)
        x = y;
    else if(x.fi == y.fi){
        x.se += y.se;
        if(x.se >= MOD)
            x.se -= MOD;
    }
}

pii BIT[N]; // <panjang,banyak cara>
int list[N]; // daftar koordinat kanan-atas
Trapezoid arr[N],arr2[N];
int n;
pii ans[N];

void Update(int x,pii val){
    for(; x <= n ; x += x & -x)
        Add(BIT[x],val);
}

pii Query(int x){
    pii res = mp(0,0);
    for(; x > 0 ; x -= x & -x)
        Add(res,BIT[x]);
    return res;
}

int ID(int x){ // mengembalikan indeks y, di mana y bilangan terbesar yang berlaku list[y] <= x
    int res = upper_bound(list,list + n + 1,x) - list;
    return res - 1;
}

int main(){
    scanf("%d",&n);
    list[0] = -1;
    
    for(int i = 1 ; i <= n ; i++){
        scanf("%d %d %d %d",&arr[i].aki,&arr[i].aka,&arr[i].bki,&arr[i].bka);
        arr[i].id = i;
        arr2[i] = arr[i];
        list[i] = arr[i].aka;
    }
    
    sort(arr + 1,arr + n + 1,ByKa);
    sort(arr2 + 1,arr2 + n + 1,ByKi);
    sort(list,list + n + 1);
    
    int it = 1;
    for(int i = 1 ; i <= n && it <= n; i++){
        while(it <= n && arr2[it].bki <= arr[i].bka){
            int idx = arr2[it].id;
            int pos = ID(arr2[it].aki);
            ans[idx] = Query(pos);
            if(ans[idx].fi == 0) // kasus LIS yang berujung di trapezoid ini
                ans[idx].se = 1; //isinya hanya trapezoid yang bersangkutan
            ans[idx].fi++;
            it++;
        }
        int idx = arr[i].id;
        int pos = ID(arr[i].aka);
        Update(pos,ans[idx]);
    }
    
    pii res = mp(0,0);
    for(int i = 1 ; i <= n ; i++)
        Add(res,ans[i]);
        
    printf("%d %d\n",res.fi,res.se);
    return 0;
}