오름차순
다이아몬드 IV의견: 0
길이 \(M\)인 양의 정수열 \(X_1, \dots , X_M\)이 주어질 때, 이 수열을 오름차순으로 만드는 것을 생각해 보자. 수열 \(X_1, \dots , X_M\)이 오름차순이라는 것은, 각 \(i\) (\(1 ≤ i ≤ M - 1\))에 대해 \(X_i ≤ X_{i+1}\)이라는 것이다.
수열 \(X\)를 오름차순으로 만들기 위해, 수열 \(X\)에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.
- 어떤 \(i\) (\(1 ≤ i ≤ M\))에 대해 \(X_i\)에 \(2\)를 곱한다.
연산을 최소 횟수로 적용해서 \(X\)를 오름차순으로 만들 때, 이 최소 횟수를 \(f(X)\)라고 하자.
길이 \(N\)의 양의 정수열 \(A_1, \dots , A_N\)과 쿼리 \(Q\)개가 주어진다. 각 쿼리에는 \(1 ≤ l ≤ r ≤ 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\)
첫 번째 줄에 \(N\)과 \(Q\)가 공백으로 구분되어 주어진다.
두 번째 줄에 \(A_1, \dots , A_N\)이 공백으로 구분되어 주어진다.
이후 \(Q\)개의 줄에 걸쳐 쿼리들이 주어진다. 각 쿼리는 \(l\)과 \(r\)이 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 쿼리들의 답을 입력 순서대로 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
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점 | 추가 제약 조건 없음. |
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
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
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 고등부 3번
평가 및 의견
오름차순
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
오름차순