백준17635 다리

작성일 | In

문제 링크

  • http://icpc.me/17635

문제 출처

  • 2019 APIO 2번

사용 알고리즘

  • Sqrt Decomposition

시간복잡도

  • $O(Q\times(\frac{M}{\sqrt N}+\sqrt N log N))$

풀이

Subtask 1 - Naive

Naive하게 구현하면 각 쿼리 당 $O(N+M)$, 총 $O(Q(N+M))$에 문제를 풀 수 있습니다.

Subtask 2 - 선형

일반적인 그래프가 아니라 선형입니다.
무게가 X인 자동차가 L에서 R로 갈 수 있다는 것은 L부터 R까지 가는 길에 있는 모든 다리의 무게 제한이 X 이상이라는 것을 의미합니다.
Minimum Segment Tree를 만들어서 1번 쿼리는 단순한 Point-Update로 처리해주고, 2번 쿼리는 이분 탐색을 이용해 왼쪽으로 최대한 갈 수 있는 곳, 오른쪽으로 최대한 갈 수 있는 곳을 찾아주면 됩니다.
1번 쿼리는 $O(\log N)$에 할 수 있고, 2번 쿼리는 이분 탐색을 이용하면 $O(\log^2 N)$에 할 수 있는데 세그먼트 트리의 루트에서 적당히 타고 내려가면 $O(\log N)$에 처리할 수도 있습니다.

Subtask 4 - 갱신 없음

쿼리와 간선을 무게와 무게 제한 내림차순으로 정렬해주면 Union-Find를 이용해 오프라인으로 쿼리를 계산할 수 있습니다. 시간 복잡도는 $O((M+Q)\log(M+Q))$입니다.

Subtask 1, 2, 4를 해결하면 43점을 받을 수 있습니다.

전체 풀이

쿼리를 B개씩 묶어서 처리해봅시다. 쿼리를 B개씩 나눈 덩어리들을 “쿼리 조각”이라고 합시다.

각 쿼리 조각에는 최대 B개의 쿼리가 있기 때문에, B개의 쿼리동안 가중치가 바뀌는 간선들은 최대 B개입니다. 쿼리 조각의 처리를 시작할 때 먼저 가중치가 바뀌는 간선들과 그렇지 않은 간선들을 분리해줍시다.

현재 쿼리 조각에 있는 쿼리를 차례대로 보면서 하나씩 처리할 것입니다.
1번 쿼리는 단순히 간선의 가중치를 바꿔주는 것으로 처리합니다. 이 행위는 각 쿼리 조각에서 최대 B번 수행합니다.
2번 쿼리들은 각 쿼리에 대해, 자동차의 무게보다 무게 제한이 크거나 같은 다리들을 모두 저장할 것입니다. 아래와 같은 느낌으로 합니다.

1
2
3
for(int i=0; i<edge.size(); i++){
  if(qry[now].limit <= weight[edge[i]]) g[now].push_back(edge[i]);
}

이 쿼리는 각 쿼리 조각에서 최대 B번 수행하고, 쿼리에 다리를 저장하는 행위는 최대 MB번합니다.
하지만 현재 쿼리 조각에서 가중치가 바뀌지 않는 간선들은 나중에 처리해도 되기 때문에 굳이 저장할 필요가 없습니다. 그러므로 각 쿼리에는 최대 B개의 다리만 저장하면 됩니다.

쿼리 조각에 있는 쿼리를 모두 훑은 후, 가중치가 바뀌지 않는 간선들을 잘 처리해야 합니다.

가중치가 바뀌지 않는 간선들을 가중치 내림차순으로 정렬한 뒤, Subtask 4와 비슷하게 Union-Find를 이용해 결과를 구해주면 됩니다.
이때 각 쿼리마다 저장해놓은 다리들도 봐줘야 하는데, 이건 해당 쿼리를 볼 때 union하고, 다음 쿼리로 넘어가기 전에 roll back해주면 됩니다.

이런 과정을 거치면 간선을 분류하는데 $O(M)$, 1번 쿼리에 최대 $O(B)$, 2번 쿼리에 최대 $O(B^2)$이 걸리고, 가중치가 바뀌지 않는 간선들을 처리할 때 $O(N \log N)$이 걸립니다.

각 쿼리 조각에서 $O(N \log N + B^2)$이 걸리므로 총 시간 복잡도는 $O(\frac{Q}{B} \times (M + B^2 + N log N))$이 됩니다.
이때 $B = \sqrt N$로 잡으면 $O(Q\times(\frac{M}{\sqrt N}+\sqrt N log N))$ 정도에 문제를 풀 수 있습니다.