[baekjoon] #7578: 공장

problem link

• To find the number of intersected cable, find B's index corresponding to A's value which means A[i].

• With the index, count how many visited machine using segment tree data structure in [index + 1, n - 1]

• Please refer this blog to understand how to find the number of intersected cable.

• The reason why I use Long type segment tree is the maximum number of intersected cable is greater than maximum value of integer.

lateinit var segTree: Array<Long>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    segTree = Array(4 * n) { 0L }

    val a = br.readLine().split(" ").map { it.toInt() }
    val b = br.readLine().split(" ").map { it.toInt() }

    val map = mutableMapOf<Int, Int>()
    for (i in 0 until n) {
        map[b[i]] = i
    }

    var answer = 0L
    for (i in 0 until n) {
        val index = map[a[i]]!!
        // count [i+1, n-1] visited machine
        val visitedCount = getSegTreeValue(0, n - 1, index + 1, n - 1, 0)
        answer += visitedCount
        // check visited
        updateSegTree(0, n - 1, index, 1, 0)
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

fun getSegTreeValue(low: Int, high: Int, qLow: Int, qHigh: Int, pos: Int): Long {
    // total overlap
    if (qLow <= low && qHigh >= high) return segTree[pos]
    // no overlap
    if (qLow > high || qHigh < low) return 0

    // partial overlap
    val mid = (low + high) / 2
    return getSegTreeValue(low, mid, qLow, qHigh, 2 * pos + 1) +
            getSegTreeValue(mid + 1, high, qLow, qHigh, 2 * pos + 2)
}

fun updateSegTree(low: Int, high: Int, index: Int, value: Int, pos: Int) {
    // leaf node
    if (low == high) {
        // update value
        if (low == index) segTree[pos] = value.toLong()
        return
    }
    // out of range
    if (index !in low..high) return

    // update in range values
    val mid = (low + high) / 2
    updateSegTree(low, mid, index, value, 2 * pos + 1)
    updateSegTree(mid + 1, high, index, value, 2 * pos + 2)
    segTree[pos] = segTree[2 * pos + 1] + segTree[2 * pos + 2]
}

Time Complexity

O(N)