주간 PS 리뷰
리뷰를 매주 쓰기로 하고 한 주만에 망해버렸다. 이번 한 주간 백준에서 푼 문제가 쿼리와 쿼리, 트쿼3 두 문제 뿐이다. 한 주간 한거라고는 유튜브보고 블로그 검색 밖에 없는 것 같다. 이번 주는 저 두 문제 리뷰로 마치고 문제를 열심히 풀어야겠다. 코포도 글로벌 라운드를 치기는 했는데 3문제 풀고 복통으로 탈주해서 -200을 먹은 라운드라 딱히 쓸 것도 없고 가만히 반성만 해야겠다. 그래도 PS 리뷰를 시작한 걸 다행이라고 생각한다. 주간 리뷰조차 안했으면 열심히 한 주간 쳐 놀아버린 것도 몰랐을 거 같다.
최근들어 PS에 대한 의욕이 예전 같지 않은 것 같다고 느꼈다. 그래도 며칠간 재미는 문제도 많이 보고 공부할것도 많이 생겼으니 초심으로 돌아가 좀 더 열심히 해봐야겠다. 잡설은 이만하고 빠르게 리뷰해야겠다.
쿼리와 쿼리
제일 먼저 xor연산의 특성을 이용해 많은 부분을 간단하게 만들 수 있다. 우선 업데이트들에서 처음 주어진 x들은 쿼리에서는 그다지 중요하지 않다. prefix xor이나 펜윅 등 마음대로 처리한 뒤 마지막 답에 xor만 해주면 된다. 쿼리에서는 주어진 범위의 업데이트를 한번에 변경한다. 이때 중요한 값은 각 업데이트의 구간들이고 특히 결국 xor의 역원은 자신과 같으므로 특정한 칸에 칠해지는 업데이트의 홀짝성만 중요하다.
관찰을 이용해 앞의 1번 종류의 쿼리 하나가 뒤의 2번 종류의 쿼리 하나에 xor하는 수를 빠르게 구해보자. 1번에서 변경하는 L번부터 R번 업데이트 중 2번에서 xor하는 s~e 안에 몇 개의 칸이 들어가는 지를 홀짝으로 구하면 된다. 오프라인으로 어떤 쌍들을 구해야 하는지를 미리 구하면 1~L-1을 구해서 1~R에서 빼는 방식으로 구간을 처리할 수 있다. 따라서 정렬 후, 1번 업데이트부터 하나씩 펜윅, 세그 등의 자료구조에 구간을 칠해준다. 그리고 쿼리마다 해당하는 값을 제때 구하면 전체 업데이트에 O(M lg N)가 걸리고 쿼리 쌍마다는 O(lg N)에 풀 수 있다. 하지만 이 방식만으로는 어차피 쿼리 쌍의 수가 최대 제곱이라 O(Q^2 lg N + M lg N)이 된다.
여기서 다른 발상을 해보자. '모든 2번 쿼리는 1번 쿼리가 모두 나온 다음에 나온다.' 라는 조건을 추가해보자. 둘의 수가 비슷하다면 앞서 말한 방식에서는 최악의 경우일 것이다. 하지만 명확하게 위 조건이 있으면 모든 변경을 한 뒤에 쿼리를 처리하면 되기 때문에 M개의 업데이트를 그냥 한번 더 한 다음에 2번 쿼리를 하나씩 처리해도 문제가 없다. 방법은 그냥 prefix xor을 M개의 업데이트에 대해서, 적용된 배열에 대해서 두 번 해주면 O(M+N)에 된다.
이게 가능한 이유는 2번 쿼리를 처리하는 중간에 1번 쿼리가 없기 때문이다. 만약 이 방법의 풀이에서 우리가 추가한 조건이 없다면 2번이 나올 때마다 O(M+N)의 시간을 들여 다시 1번 쿼리들을 업데이트 해야 할 것이다. 이경우는 121212... 같은 데이터에서 제곱이 될 것이다. 그런데 이 방식에서 O(M+N)의 업데이트를 하지않고 뻐기면 무슨 일이 생기는지 살펴보자. 현재 x번째 쿼리까지의 1번 쿼리들이 처리되어 있고 우리는 y번째 있는 2번 쿼리에 대한 답을 중간의 갱신 없이 야매로 구했다. 이때 답이 틀리는 원인은 x+1~y-1사이에 있는 1번 쿼리가 y번째의 2번 쿼리에게 영향을 주지 못했기 때문이다. 우리는 앞서 특정 1번과 2번 쿼리에 대한 쌍을 빠르게 처리하는 방법을 찾았다. 그렇다면 적당한 지점에서 O(M+N)으로 싹 업데이트를 하고 사이사이의 적은 수의 쌍들은 첫 번째 방법으로 구해서 합쳐준다면?
대충 버킷을 사용해서 B번마다 한 번씩 업데이트를 한다고 가정하자. Q/B개의 구간으로 나눠지고 각각에서 최대 B^2개의 쿼리 쌍이 나온다. 시간복잡도로 이를 분석하면, O(QB lg N + Q*(N+M)/B)이 되며 최적의 B를 잘 찾아 넣으면 AC를 받는다. 참고로 시간 커팅을 잘 해야한다. 세그 등의 자료구조라고 말은 했지만 펜윅을 써야 상수가 안전하다. 참고로 구간에 v를 더하는 연산은 레이지 없이 할 수 있으며 펜윅 2개로 인덱스 i에 대해 ai+b꼴의 계수를 관리하면 할 수 있다. 나는 여기서는 홀짝만 관리하면 되는 관계로 (a&i) ^ b 로 썼다.
트리와 쿼리 3
풀이가 굉장히 많다. 단순한 풀이로는 HLD+세그가 있겠다. HLD로 체인을 자른 뒤 체인에서 가장 위의 수를 찾고, 업데이트를 그냥 해주면 로그 제곱에 무난히 된다. 나는 다른 풀이로 풀었는데 세그 각 노드에 셋을 관리했다. 좀 더 자세히 설명해 보자면, 우선 트리를 오일러 투어로 펼친다. 그럼 어떤 노드를 칠하는 연산은 그 아래 서브트리의 노드들의 1번 정점으로의 경로 상에 있음/없음을 바꾸는 연산이 된다. 우리가 해야 하는 연산은 어떤 노드 위에 있는(하얗게 칠해진) 노드 중 가장 높은 원소를 찾는 연산이다. 결론적으로는 구간에 어떤 숫자를 추가, 삭제하고 어떤 칸의 숫자들을 조회하는 연산이 필요하다. 따라서 세그먼트 트리를 만들고 세그의 각 노드를 셋이나 PQ등으로 잘 만들어주면 역시 로그제곱에 HLD 없이 풀 수 있다.