insertion sort 썸네일형 리스트형 BOJ)13274 수열 문제: icpc.me/13274 정렬 된 수열에서 쿼리를 처리하는 문제이다. 쿼리 l r x 는 l~r 구간의 원소에 x를 더해준 뒤 다시 정렬하는 쿼리이다. n이 10만이고 쿼리가 1000개 인데 매번 퀵소트를 실행해주면 1억xlog10만 이므로 1초의 제한 시간에 간당간당한 느낌이다. 따라서 좀 더 빠른 소팅 방법이 필요한데, 정렬 된 구간에서 l~r에 x를 더하게 되면, l~r의 구간은 오름차순을 유지할 것이며, 전체의 구간에서 l~r의 구간을 제외한 구간 역시 오름차순을 유지할 것이다. 이렇게 정렬 된 두 구간에서 서로 가장 앞 원소를 비교하며 insertion sort를 하면 소팅을 O(N)의 시간에 해결할 수 있다. 1234567891011121314151617181920212223242526.. 더보기 이전 1 다음