원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
오름차순
원제: 오름차순
문제
길이 인 양의 정수열 이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자. 수열 이 오름차순이라는 것은, 각 ()에 대해 이라는 것이다.
수열 를 오름차순으로 만들기 위해, 수열 에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.
- 어떤 ()에 대해 에 2를 곱한다.
연산을 최소 횟수로 적용해서 를 오름차순으로 만들 때, 이 최소 횟수를 라고 하자.
길이 의 양의 정수열 과 쿼리 개가 주어진다. 각 쿼리에는 을 만족하는 정수 과 이 주어진다. 해당 쿼리에 대한 답은 이다. 은 의 번째 원소부터 번째 원소까지로 이루어진 부분 수열을 의미한다.
각 쿼리에 대한 답을 구하여라.
제약 조건
- 주어지는 모든 수는 정수이다.
- ()
- 모든 쿼리에 대해
부분문제
- (5점) ,
- (7점)
- (28점) 모든 쿼리에 대해
- (10점) ()
- (5점) ()
- (10점) 를 만족하는 0 이상의 정수 가 존재 ()
- (35점) 추가 제약 조건 없음
입력 형식
첫 번째 줄에 과 가 공백으로 구분되어 주어진다.
두 번째 줄에 이 공백으로 구분되어 주어진다.
이후 개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리는 과 이 공백으로 구분되어 주어진다.
출력 형식
개의 줄에 걸쳐 쿼리들의 답을 입력 순서대로 출력한다.
예제
예제 1
10 5 5 2 7 3 2 9 6 3 3 5 3 9 1 10 1 8 2 4 8 9
14 27 19 2 0
예제 2
10 5 2 8 4 9 10 8 5 3 7 7 2 8 1 10 3 3 1 3 8 10
7 11 0 1 0