[BOJ] 13547 수열과 쿼리 5 - P2

문제풀이

1. 쿼리를 (l / sqrt(N))에 대하여 오름차순, r에 대하여 오름차순 정렬한다.
2. 이전 쿼리의 l, r과 현재 쿼리의 l, r에서 변동량을 기록한다.

---

주의사항

---

소요시간

30분

---

package 백준.Platinum.P2.p13547_수열과쿼리5

import kotlin.math.sqrt

fun main() {
    val N = readln().toInt()
    val A = readln().trim().split(" ").map(String::toInt)
    val M = readln().toInt()
    val Q = Array(M) { idx -> readln().trim().split(" ").map(String::toInt).let { Triple(idx, it[0] - 1, it[1] - 1) } }
    val sqrtN = sqrt(N.toDouble()).toInt()
    Q.sortWith(compareBy({ it.second / sqrtN }, { it.third }))
    val count = IntArray(A.max() + 1)
    var pl = 0
    var pr = -1
    var numCount = 0
    val result = IntArray(M)
    for ((idx, l, r) in Q) {
        if (pl < l) {
            for (i in pl until l) {
                if (count[A[i]] == 1) numCount--
                count[A[i]]--
            }
        }
        if (pl > l) {
            for (i in l until pl) {
                if (count[A[i]] == 0) numCount++
                count[A[i]]++
            }
        }
        if (pr < r) {
            for (i in (pr + 1)..r) {
                if (count[A[i]] == 0) numCount++
                count[A[i]]++
            }
        }
        if (pr > r) {
            for (i in (r + 1)..pr) {
                if (count[A[i]] == 1) numCount--
                count[A[i]]--
            }
        }
        pl = l
        pr = r
        result[idx] = numCount
    }
    println(result.joinToString("\n"))
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P2/p13547_%EC%88%98%EC%97%B4%EA%B3%BC%EC%BF%BC%EB%A6%AC5/p13547_%EC%88%98%EC%97%B4%EA%B3%BC%EC%BF%BC%EB%A6%AC5.kt

---

문제링크

https://www.acmicpc.net/problem/13547

---

회고

Mo's 알고리즘을 학습하며 푼 문제