루미 알고리즘

#1097플래티넘오름차순오름차순

KOI 2024 1차코딩고등부 3번출제 김준원이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

오름차순

원제: 오름차순

문제

길이 MM인 양의 정수열 X1,…,XMX_1, \ldots, X_M이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자. 수열 X1,…,XMX_1, \ldots, X_M이 오름차순이라는 것은, 각 ii (1≤i≤M−11 \le i \le M - 1)에 대해 Xi≤Xi+1X_i \le X_{i+1}이라는 것이다.

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

  • 어떤 ii (1≤i≤M1 \le i \le M)에 대해 XiX_i에 2를 곱한다.

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

길이 NN의 양의 정수열 A1,…,ANA_1, \ldots, A_N과 쿼리 QQ개가 주어진다. 각 쿼리에는 1≤l≤r≤N1 \le l \le r \le N을 만족하는 정수 ll과 rr이 주어진다. 해당 쿼리에 대한 답은 f(Al,…,Ar)f(A_l, \ldots, A_r)이다. Al,…,ArA_l, \ldots, A_r은 AA의 ll번째 원소부터 rr번째 원소까지로 이루어진 부분 수열을 의미한다.

각 쿼리에 대한 답을 구하여라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤250 0001 \le N \le 250\,000
  • 1≤Q≤250 0001 \le Q \le 250\,000
  • 1≤Ai≤1091 \le A_i \le 10^9 (1≤i≤N1 \le i \le N)
  • 모든 쿼리에 대해 1≤l≤r≤N1 \le l \le r \le N

부분문제

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

입력 형식

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

두 번째 줄에 A1,…,ANA_1, \ldots, A_N이 공백으로 구분되어 주어진다.

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

출력 형식

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

예제

예제 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

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.