[BOJ] 10713번: 기차 여행

https://www.acmicpc.net/problem/10713

여행의 흐름을 보면 결국 각 도로를 사용하는 횟수는 고정입니다. 횟수가 정해지면 IC 티켓을 사는게 나은지, 안사는게 나은지를 알 수 있는데, 이 횟수를 정직하게 1씩 더해가며 체크한다면 1 -> N -> 1 -> N -> 1 -> .. 과 같은 상황에서 O(NM)이 걸립니다. segment tree의 lazy propagation으로 O(MlgN)에 처리할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/10713.cpp