Mo's Algorithm dengan Update

Setelah sekian lama gak ngeblog , akhrinya ngeblog lagi. Jadi sebenarnya saya ingin ngeblog pelatnas 3 dlu sih niatnya tapi karena foto-foto selama pelatnas 3 belum dikirimkan jadi ditunda aja dlu :). 
Alasan pengen ngeblog pelatnas 3 walaupun sudah dibuat blognya karna banyak hal-hal lucu yang tidak tertuliskan di blog , dan juga blog saya gak formal :p jadi bisa nulis blak-blakan.

Jadi ini bakal jadi post pertama saya di blog ini yang ngebahas tentang algoritma. Kenapa saya milih algo ini karena menurut saya topik ini dikit resourcenya di internet. Kalo yang mainstream kayak segment tree,BIT,dll kan bisa dipelajari di internet. Topik ini agak advanced dan juga jarang digunakan jadi bagi yang bingung wajar aja. Cukup basa-basinya langsung aja ke pembahasan algoritmanya.

Pre-requisite : tau cara kerja Mo's (kalo masih belum tau coba aja cari di google ini banyak kok resourcenya)

Anggap query 1 sebagai query update dan query 2 untuk menanyakan jawaban.

Step 1: untuk setiap input query 1 dan query 2 kita bedakan dlu.
Step 2: untuk setiap query 2, kita masukkan mereka kedalam struct , yang dimasukan adalah {L/B,R/B,time} dimana time itu berarti sudah berapa banyak query 1 yang dilakukan saat query 2 ditanyakan dan B itu size dari blok, nanti kompleksitasnya bakal jadi O(N/B * N/B * Q)
Step 3: sort increasing dari blok terkiri jika sama blok terkanan jika sama waktu querynya.

setelah semua hal ini dilakukan maka kita dapat menjalankan Mo's algorithm yang biasa

//Mo's biasa
int L = q[i].L, R = q[i].R;
while(currentL < L) {
 //do something
 currentL++;
}
while(currentL > L) {
 //do something
 currentL--;
}
while(currentR <= R) {
 //do something
 currentR++;
}
while(currentR > R+1) {
 //do something
 currentR--;
}

tapi karna sekarang ada query jadi kita harus tambahkan time juga jadi

int L = q[i].L, R = q[i].R, Time = q[i].T;
while(currentL < L) {
 //do something
 currentL++;
}
while(currentL > L) {
 //do something
 currentL--;
}
while(currentR <= R) {
 //do something
 currentR++;
}
while(currentR > R+1) {
 //do something
 currentR--;
}
// kita tambahkan yang buat time
while(currentTime > Time) {
 //do something 
 currentTime--;
}
while(currentTime < Time) {
 //do something
 currentTime++;
}

nah algoritmanya cuma sampai begitu , bagaimana dengan perhitungan kompleksitasnya ?

Mari kita hitung satu satu
-currentR: pointer currentR bergerak sebanyak N*(N/B) yang artinya berjalan N kali untuk setiap blok dikiri , tidak hanya itu currentR juga bergerak sebanyak Q*B karena untuk setiap query bisa saja yang ditanyakan ada di ujung kiri blok dan ujung kanan blok secara berselang-seling. total = N * (N/B) + Q* B

-currentL: pointer currentL bergerak sebanyak Q*B dengan alasan yang sama untuk currentR dimana currentL dapat bergerak ke ujung kiri dan ujung kanan secara berselang-seling. total = Q * B

-currentTime: pointer current time hanya berubah apabila terjadi pergantian blok L atau blok R sehingga kompleksitasnya menjadi (N/B) (untuk setiap blok kiri) * (N/B) (untuk setiap blok kanan) * Q (waktu). total = (N/B)^2 * Q

kita jumlahkan semua maka jadi O(Q*B + (N/B)^2 * Q) , nah sekarang bagaimana cara mencari B yang tepat maka kita dapat gunakan persamaan Q * B = (N/B)^2 * Q, kenapa harus sama karena kita ingin mereka seimbang kalo gak sama maka nanti kompleksitasnya ada 1 yang lebih besar dari yang lain dan cuma itu yang dihitung. dengan persamaan tersebut dapat kita hitung bahwa B yang memenuhi adalah N^(2/3) , jadilah kompleksitas akhir dengan O(Q * N^(2/3))

Sudah mengerti kan ,Mari kita langsung ke contoh soal (SPOJ-ADAUNIQ)

Deskripsi singkatnya, diberikan N buah bilangan dan Q buah query, querynya ada 2 jenis , query 1 ngubah bilangan di indeks ke Xi jadi A , query ke 2 keluarkan banyak bilangan yang unik(frekuensinya 1) di rentang L sampai R inklusif.

Caranya dapat menggunakan cara diatas yaitu Mo's algorithm dengan update , kita siapin sebuah array cnt dimana jika array cnt itu menjadi 1 maka jawabannya bertambah satu apabila keluar dari range 1 maka jawabannya berkurang 1 . Solusi dapat dilihat di sini.

Saya belum berhasil menemukan soal-soal lain yang menggunakan algoritma ini tapi yang pasti apabila permasalahan tersebut dapat diselesaikan dengan Mo's tanpa update maka apabila ditambahkan update dapat diselesaiakan dengan algo ini. Apabila ada yang mau memberikan soal yang menggunakan algo ini dapat mengirimkan ke saya biar bisa saya masukin di blog.

Akhir kata saya ucapkan terima kasih , karena ini pertama kalinya saya nulis post tentang pembahasan algoritma , jika ada banyak kekurangan dapat disampaikan kepada saya agar kedepannya kekurangan yang sama tidak terulang. Terima kasih.