¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#7020
Subtarea

오름차순 4s 1024MB

Problemas

길이 M인 양의 정수열 X_1, \dots, X_M이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자.

수열 X_1, \dots, X_M이 오름차순이라는 것은, 각 i (1 \le i \le M-1)에 대해 X_i \le X_{i+1}이라는 것이다.

수열 X를 오름차순으로 만들기 위해, 수열 X에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

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

연산을 최소 횟수로 적용해서 X를 오름차순으로 만들 때, 이 최소 횟수를 f(X)라고 하자.

길이 N의 양의 정수열 A_1, \dots, A_N과 쿼리 Q개가 주어진다.

각 쿼리에는 1 \le l \le r \le N을 만족하는 정수 l과 r이 주어진다. 해당 쿼리에 대한 답은 f(A_l, \dots, A_r)이다.

A_l, \dots, 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


Entrada

첫 번째 줄에 N과 Q가 공백으로 구분되어 주어진다.

두 번째 줄에 A_1, \dots, A_N이 공백으로 구분되어 주어진다.

이후 Q개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리는 l과 r이 공백으로 구분되어 주어진다.


Salida

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


Subtarea

# Puntaje Condición
#15

N \le 10,000, Q \le 10,000

#27

N \le 10,000

#328

모든 쿼리에 대해 r = N

#410

A_i \ge A_{i+1} (1 \le i \le N-1)

#55

A_i \le 2 (1 \le i \le N)

#610

A_i = 2^{k_i} 를 만족하는 0이상의 정수 k_i가 존재 (1 \le i \le N)

#735

추가 제약 조건 없음


Ejemplo #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

Ejemplo #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


Fuente

KOI 1차 2024 고3

Debes iniciar sesión para escribir código.