Codeforces Round #717 (Div. 2) D. cut

못풀고 에디토리얼 봤다. 보자마자 이거쓰면 풀리겠네 라고 바로 생각하게 되는 문제.

https://codeforces.com/contest/1516/problem/D

 

풀이는 sparse table이다. 저 단어 하나만 떠올려도 문제를 풀 수 있다.

sparse table문제를 진짜 오랜만에 만났는데, 복습해야 할 거 같다. dp도 유형이 많다.

 

곱이 lcm이라는건 결국 구간내의 모든 원소들이 서로소여야 한다.

그럼 투포인터로 dp[x][0]-> x번째 원소부터 출발했을때 갈 수 있는 최대 거리

로 정의를 하면 sparse table로 처리할 수 있고, 구간 쿼리를 logn에 처리할 수 있다.

처음에 보자마자 mo's로 잘짜면 되겠는데? 라는 생각을 했다. 
이제 업데이트 없는 구간 쿼리는 스파스 테이블로 될까? 부터 생각해야겠다.

끝.