문제풀이
- |S|의 누적합을 구한다.
- 1 ~ N요소가 S에 포함되는 구간을 구하고, 그 구간 사이의 |S|의 합을 구한다.
주의사항
- Int형 오버플로우 주의 -> Long
소요시간
14분
package AtCoder.ProblemList.Difficulty1100.SetAddQuery
const val EMPTY = -1
fun main() {
val (N, Q) = readln().trim().split(" ").map(String::toInt)
val X = readln().trim().split(" ").map(String::toInt)
val S = LongArray(Q)
val prevIdxArr = IntArray(N) { EMPTY }
var count = 0
val result = LongArray(N)
for (i in 0 until Q) {
val idx = X[i] - 1
val prevIdx = prevIdxArr[idx]
if (prevIdx == EMPTY) {
count++
prevIdxArr[idx] = i
} else {
count--
result[idx] += S[i - 1] - S.getOrElse(prevIdx - 1) { 0 }
prevIdxArr[idx] = EMPTY
}
S[i] += S.getOrElse(i - 1) { 0 } + count
}
for (i in 0 until N) {
if (prevIdxArr[i] != -1) result[i] += S[Q - 1] - S.getOrElse(prevIdxArr[i] - 1) { 0 }
}
println(result.joinToString(" "))
}