문제 링크 usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요... 풀 때 사진 참고하세요. 문제 번역 \(1\)부터 \(N\)까지 높이에 대한 내림차순으로 번호가 매겨진 \(N\)개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) \(M\)개의 운하는 서로 다른 마을을 단방향으로 연결합니다. \(i\)번째 운하(\(1\le i\le M\))은 높은 \(S_i\)에서 낮은 \(E_i\)로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다. 비버 Bitaro의 \(N\)명의 친구들은 \(N\)개의 마을에 살고 있습니다. Bitaro는 \(Q\)번의 파티를 열며, 친구들을 초대할 것입니다. \(j\)번째 파티에는 \(Y_j..

문제 링크 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: $N ≤ 3\ 000, Q ≤ 3\ 000$ (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 $ ≤ 10^5, Z_j =0$ (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자료구조들이 있을 것이다. 그렇게 다음의 3가지 풀이가 있다: Merge sort tr..