일단 O(NK) 풀이는 아시는것 같으니 효율적으로 구간 [a, a + K)를 반전하는 방법을 알려드릴게요.
https://wcipeg.com/wiki/Prefix...
제가 푼 방식은 여기서 나오는 difference array하고 개념적으로 비슷합니다 (대신 이 문제는 xor array)
주어진 배열 A = [1, 1, 0, 0, 0, 1]
B[i] = A[i] ^ A[i - 1], 여기서 A[-1] = 0
즉, B = [1, 0, 1, 0, 0, 1]
A에서 구간 [a, b) 를 반전하는건 B[a], B[b]를 반전하는것과 똑같습니다.
예를 들어서 A에서 구간 [1, 4)를 반전하면 B는 [1, 1, 1, 0, 1, 1]이 되죠.
B를 다시 A 형태 (C라고 하죠) 복구하는건 다음과 같이 할 수 있습니다.
C[0] = B[0], C[i] = B[i] ^ C[i - 1]
그래서 [1, 1, 1, 0, 1, 1]을 복구해보면 C = [1, 0, 1, 1, 0, 1]이 됩니다.
보시다시피 복구한 C는 A에서 [1, 4)를 반전한것과 똑같죠.
Green55 6년 전
아무리 생각해도 그리디 + 시뮬레이션으로 직접 해보는 풀이 말고는 생각나지가 않습니다..
작은 힌트라도 주실분 없으신가요 ㅠㅠ