길이 \(M\)인 양의 정수열 \(X_1, . . . , X_M\)이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자. 수열 \(X_1, . . . , X_M\)이 오름차순이라는 것은, 각 \(i (1 \le i \le M − 1)\)에 대해 \(X_i ≤ X_{i+1}\)이라는 것이다.
  수열 \(X\)를 오름차순으로 만들기 위해, 수열 \(X\)에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

• 어떤 \(i (1 \le i \le M)\)에 대해 \(X_i\)에 2를 곱한다.

  연산을 최소 횟수로 적용해서 \(X\)를 오름차순으로 만들 때, 이 최소 횟수를 \(f(X)\)라고 하자
  길이 \(N\)의 양의 정수열 \(A_1, . . . , A_N\)과 쿼리 \(Q\)개가 주어진다. 각 쿼리에는 \(1 \le l \le r \le N\)을 만족하는 정수 \(l\)과 \(r\)이 주어진다.    해당 쿼리에 대한 답은 \(f(A_l , . . . , A_r)\)이다. \(A_l , . . . , A_r\)은 \(A\)의 \(l\)번째 원소부터 \(r\)번째 원소까지로 이루어진 부분 수열을 의미한다.
  각 쿼리에 대한 답을 구하여라.

제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le N \le 250 000\)
• \(1 \le Q \le 250 000\)
• \(1 \le A_i \le 10^9 (1 \le i \le N)\)
• 모든 쿼리에 대해 \(1 \le l \le r \le N\)

부분문제
1. (5점) \(N \le 10 000, Q \le 10 000\)
2. (7점) \(N \le 10 000\)
3. (28점) 모든 쿼리에 대해 \(r = N\)
4. (10점) \(A_i \ge A_{i+1} (1 \le i \le N − 1)\)
5. (5점) \(A_i \le 2 (1 \le i \le N)\)
6. (10점) \(A_i = 2_{k_i}\)를 만족하는 0 이상의 정수 \(k_i\)가 존재 \((1 \le i \le N)\)
7. (35점) 추가 제약 조건 없음

첫 번째 줄에 \(N\)과 \(Q\)가 공백으로 구분되어 주어진다.
두 번째 줄에 \(A_1, . . . , A_N\)이 공백으로 구분되어 주어진다.
이후 \(Q\)개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리는 \(l\)과 \(r\)이 공백으로 구분되어 주어진다

\(Q\)개의 줄에 걸쳐 쿼리들의 답을 입력 순서대로 출력한다

	작성자	제목(댓글)
글이 없습니다.

문제 게시판

새 글 작성

2024KOI1차