만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 13547 수열과 쿼리 5

23 Jun 2021

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

길이 N의 수열이 주어졌을때 쿼리 i j 가 주어지면 A[i] - A[j] 에 존재하는 서로 다른 수의 개수를 출력하는 문제이다. 쿼리의 수가 많고 입력 수열에 변화가 없는 오프라인 쿼리이기 때문에 mo’s 알고리즘을 사용하였다. 앞에서 배운 개념에 약간의 변화를 줘야하는데 서로 다른 수의 개수를 세줘야 하기 때문이다. 그 외에는 평방 분할을 한 후 정렬해 쿼리를 처리해주면 된다는 것만 신경쓰면 된다.

func minus(s: Int, e: Int, val: inout Int) {
    for i in s...e {
        count[A[i]] -= 1
        if count[A[i]] == 0 {val -= 1}
    }
}

func plus(s: Int, e: Int, val: inout Int) {
    for i in s...e {
        if count[A[i]] == 0 {val += 1}
        count[A[i]] += 1
    }
}

구간이 변할때마다 구간이 증가하면 plus함수를 감소하면 minus함수를 호출할 것인데 각각의 함수는 서로 다른 수의 갯수이기 때문에 새롭게 수가 0에서 1로 증가할 경우와 기존의 수가 1에서 0으로 감소하는 경우 두가지가 발생하면 전체 result에 값을 1 변동되게 하였다. 그 외에는 count라는 배열을 통해서 각 수가 세어진 횟수를 저장해두는 방식으로 구현했다.

파일의 입력이 크기때문에 fread를 해줘야 시간초과가 안난다. 관련 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였다.
<출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>

/*
 fread 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였습니다.
 <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>
*/

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

let fIO = FileIO()
let n = fIO.readInt(), sqrtN = Int(sqrt(Double(n)))
var A = Array(repeating: 0, count: n+1)
for i in 1...n {
    A[i] = fIO.readInt()
}
let m = fIO.readInt()
var query:[(Int, Int, Int)] = Array(repeating: (0, 0, 0), count: m)
var count:[Int] = Array(repeating: 0, count: 1_000_001)

func minus(s: Int, e: Int, val: inout Int) {
    for i in s...e {
        count[A[i]] -= 1
        if count[A[i]] == 0 {val -= 1}
    }
}

func plus(s: Int, e: Int, val: inout Int) {
    for i in s...e {
        if count[A[i]] == 0 {val += 1}
        count[A[i]] += 1
    }
}

for i in 0..<m {
    query[i] = (fIO.readInt(), fIO.readInt(), i)
}
query.sort(by: {$0.1 < $1.1})
query.sort(by: {$0.0/sqrtN < $1.0/sqrtN})

var queryResult = Array(repeating: 0, count: m)
var result = 0, ps = query[0].0, pe = query[0].1
plus(s: ps, e: pe, val: &result)
queryResult[query[0].2] = result
for i in 1..<query.count {
    let curr = query[i]
    if curr.0 < ps {plus(s: curr.0, e: ps-1, val: &result)}
    else if curr.0 > ps {minus(s: ps, e: curr.0-1, val: &result)}
    if curr.1 > pe {plus(s: pe+1, e: curr.1, val: &result)}
    else if curr.1 < pe {minus(s: curr.1+1, e: pe, val: &result)}
    ps = curr.0
    pe = curr.1
    queryResult[curr.2] = result
}

var str = ""
for i in 0..<queryResult.count {
    str += "\(queryResult[i])\n"
}
print(str)

Related posts