DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

포

문제로 돌아가기

해설

한 줄에서의 조건 한 행에 기물이 ttt개 있고, 가장 왼쪽과 오른쪽 기물의 열을 L,RL,RL,R이라고 하자.

  • t≤1t\leq1t≤1이면 가로로 잡을 수 없다.
  • t=2t=2t=2이면 LLL의 왼쪽 또는 RRR의 오른쪽에 있는 빈칸에서만 잡을 수 있다. 두 기물 사이에서는 어느 방향에도 기물이 두 개 있지 않다.
  • t≥3t\geq3t≥3이면 모든 빈칸에서 잡을 수 있다. 빈칸의 양쪽에 나뉜 기물 중 적어도 한쪽에는 두 개 이상 있기 때문이다.

열에서도 같은 조건이 성립한다. 따라서 각 행과 열에서 기물의 개수, 첫 위치, 마지막 위치만 저장하면 된다.

가로를 먼저 세기 행마다 가로로 잡을 수 있는 빈칸을 먼저 답에 더한다. 기물이 두 개면 (L−1)+(M−R)(L-1)+(M-R)(L−1)+(M−R)개, 세 개 이상이면 M−tM-tM−t개이다. 이후에는 아직 세지 않은 빈칸에서만 세로 조건을 확인한다.

  • t=0t=0t=0: 구간 [1,M][1,M][1,M].
  • t=1t=1t=1: 구간 [1,L−1][1,L-1][1,, .

끝점이 뒤집힌 빈 구간은 무시한다. 이 구간들은 모두 기물이 없는 칸만 포함한다.

행 스위핑과 펜윅 트리 현재 행에서 세로로 잡을 수 있는 열을 111, 나머지를 000으로 표시하여 펜윅 트리에 저장한다. 기물이 000개 또는 111개인 열은 항상 000, 세 개 이상인 열은 항상 111이다. 기물이 정확히 두 개인 열의 첫 행과 마지막 행을 U,DU,D라 하면, 행 번호가 보다 작거나 보다 클 때만 이다.

따라서 두 기물 열은 처음에 111로 두고, UUU행의 질의를 처리하기 전에 000으로, D+1D+1D+1행 전에 다시 111로 바꾼다. D=ND=N이면 두 번째 이벤트는 필요 없다. 세 개 이상인 열의 기물 위치에도 이 저장되지만, 질의 구간에는 기물이 없으므로 문제가 없다.

이벤트를 행 번호로 정렬하고 위에서 아래로 순회한다. 각 행의 이벤트를 먼저 적용한 뒤, 아직 세지 않은 최대 두 구간의 합을 답에 더한다. 이렇게 하면 가로 또는 세로로 잡을 수 있는 빈칸이 정확히 한 번씩 계산된다.

복잡도와 자료형 이벤트 수는 KKK 이하이다. 시간 복잡도는 O(N+M+Klog⁡(K+1)+Klog⁡(M+1)+Nlog⁡(M+1))O(N+M+K\log(K+1)+K\log(M+1)+N\log(M+1))O(N+M+Klog(K+1), 공간 복잡도는 이다. 답은 이므로 답과 격자 크기 곱은 64비트 정수로 계산한다. 행·열 합과 인덱스는 이하이다. 생성기에서 사용하는 칸 번호도 미만이므로 64비트에 들어간다.

서브태스크 1은 모든 칸을 순회하며 각 행과 열의 조건을 직접 검사한다. 시간과 공간은 O(NM+N+M+K)O(NM+N+M+K)O(NM+N+M+K)이며 NM≤10 000NM\leq10\,000NM≤10000에서 충분하다. 서브태스크 2는 위 스위핑을 사용한다.

Solution written by GPT6

L
−
1]
[L+1,M][L+1,M][L+1,M]
  • t=2t=2t=2: 구간 [L+1,R−1][L+1,R-1][L+1,R−1].
  • t≥3t\geq3t≥3: 남는 구간이 없다.
  • U,D
    UUU
    DDD
    111
    D
    =
    N
    111
    +
    Klog(M+
    1)+
    Nlog(M+
    1))
    O(N+M+K)O(N+M+K)O(N+M+K)
    0≤answer≤NM−K<2.5⋅10110\leq\mathrm{answer}\leq NM-K<2.5\cdot10^{11}0≤answer≤NM−K<2.5⋅1011
    500 000500\,000500000
    NMNMNM