Problem Solving

[수열과 쿼리 1](/posts/algorithm/ps/260221_algorithm_boj-13537-%EC%88%98%EC%97%B4%EA%B3%BC-%EC%BF%BC%EB%A6%AC-1/)과 비슷한데, 업데이트 쿼리가 추가되었다.

부분수열에서 물어보는 쿼리가 있으니, 세그먼트 트리가 먼저 생각이 난다.

구간 최솟값을 번 구하는 문제이다.

어떤 트리가 있고, 간선 양쪽의 정점의 최대공약수가 1이 아니어야한다.

bitwise and들의 합과, 합들의 bitwise and 값을 구해야한다.

오늘도 찾아온 게임이론 문제이다.

이고, 와 서로소인 자연수의 개수 인 것 같다.

최대한 괄호를 제거해야 한다.

함수 가 주어질 때, 최대 번 합성한 값을 구해야 한다.

가중치가 없으니, 간단한 BFS로 풀릴 것 같다. 시간복잡도는 이다.