한 줄에서의 조건 한 행에 기물이 개 있고, 가장 왼쪽과 오른쪽 기물의 열을 이라고 하자.
열에서도 같은 조건이 성립한다. 따라서 각 행과 열에서 기물의 개수, 첫 위치, 마지막 위치만 저장하면 된다.
가로를 먼저 세기 행마다 가로로 잡을 수 있는 빈칸을 먼저 답에 더한다. 기물이 두 개면 개, 세 개 이상이면 개이다. 이후에는 아직 세지 않은 빈칸에서만 세로 조건을 확인한다.
끝점이 뒤집힌 빈 구간은 무시한다. 이 구간들은 모두 기물이 없는 칸만 포함한다.
행 스위핑과 펜윅 트리 현재 행에서 세로로 잡을 수 있는 열을 , 나머지를 으로 표시하여 펜윅 트리에 저장한다. 기물이 개 또는 개인 열은 항상 , 세 개 이상인 열은 항상 이다. 기물이 정확히 두 개인 열의 첫 행과 마지막 행을 라 하면, 행 번호가 보다 작거나 보다 클 때만 이다.
따라서 두 기물 열은 처음에 로 두고, 행의 질의를 처리하기 전에 으로, 행 전에 다시 로 바꾼다. 이면 두 번째 이벤트는 필요 없다. 세 개 이상인 열의 기물 위치에도 이 저장되지만, 질의 구간에는 기물이 없으므로 문제가 없다.
이벤트를 행 번호로 정렬하고 위에서 아래로 순회한다. 각 행의 이벤트를 먼저 적용한 뒤, 아직 세지 않은 최대 두 구간의 합을 답에 더한다. 이렇게 하면 가로 또는 세로로 잡을 수 있는 빈칸이 정확히 한 번씩 계산된다.
복잡도와 자료형 이벤트 수는 이하이다. 시간 복잡도는 , 공간 복잡도는 이다. 답은 이므로 답과 격자 크기 곱은 64비트 정수로 계산한다. 행·열 합과 인덱스는 이하이다. 생성기에서 사용하는 칸 번호도 미만이므로 64비트에 들어간다.
서브태스크 1은 모든 칸을 순회하며 각 행과 열의 조건을 직접 검사한다. 시간과 공간은 이며 에서 충분하다. 서브태스크 2는 위 스위핑을 사용한다.
Solution written by GPT6