루미 알고리즘

#1139플래티넘극솟값 제거극솟값 제거

KOI 2026 2차코딩고등부 2번출제 장근영이 문제가 어렵다면 — 배우는 순서 보기

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

극솟값 제거

원제: 극솟값 제거

문제

서로 다른 정수로 이루어진 길이 NN의 수열 A=[A1,A2,⋯ ,AN]A = [A_1, A_2, \cdots, A_N]이 주어진다.

수열 BB에 대해, 다음 과정을 한 번의 변화라고 하자.

  • B=[B1,B2,⋯ ,BK]B = [B_1, B_2, \cdots, B_K]라고 하자. 각 정수 ii (2≤i≤K−1)(2 \le i \le K - 1)에 대하여, Bi−1>Bi<Bi+1B_{i-1} > B_i < B_{i+1}를 만족할 때 BiB_i를 제거할 원소라고 하자. 수열 BB에서 제거할 원소들을 모두 동시에 제거한 뒤, 남은 원소들을 순서를 유지하여 다시 붙인다.

예를 들어, 수열 [5,1,3,2,4][5, 1, 3, 2, 4]에 변화를 33번 적용하면 다음과 같이 변한다.

[5,1,3,2,4]→[5,3,4]→[5,4]→[5,4][5, 1, 3, 2, 4] \to [5, 3, 4] \to [5, 4] \to [5, 4]

QQ개의 쿼리가 주어진다. 각 쿼리는 세 정수 ll, rr, tt로 표현할 수 있다. 각 쿼리 (l,r,t)(l, r, t)에 대하여, 수열 [Al,Al+1,⋯ ,Ar][A_l, A_{l+1}, \cdots, A_r]에 변화를 tt번 적용한 후, 이 수열에 남아 있는 원소의 개수를 구하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤200 0001 \le N \le 200\,000
  • 1≤Q≤200 0001 \le Q \le 200\,000
  • 수열 AA는 1,2,⋯ ,N1, 2, \cdots, N의 순열이다. 즉, {A1,A2,⋯ ,AN}={1,2,⋯ ,N}\{A_1, A_2, \cdots, A_N\} = \{1, 2, \cdots, N\}
  • 각 쿼리에 대하여, 1≤l≤r≤N1 \le l \le r \le N
  • 각 쿼리에 대하여, 1≤t≤N1 \le t \le N

부분문제

  1. (6점) N≤5 000N \le 5\,000; 각 쿼리에 대하여, l=1l = 1과 r=Nr = N을 만족한다.
  2. (11점) 각 쿼리에 대하여, l=1l = 1과 r=Nr = N을 만족한다.
  3. (6점) 각 쿼리에 대하여, t=1t = 1
  4. (12점) 각 쿼리에 대하여, t=Nt = N
  5. (7점) 어떤 정수 pp (1≤p≤N1 \le p \le N)가 존재하여 다음 조건을 모두 만족한다.
    • 정수 ii (1≤i≤p−1)(1 \le i \le p - 1)에 대하여 Ai>Ai+1A_i > A_{i+1}
    • 정수 ii (p≤i≤N−1)(p \le i \le N - 1)에 대하여 Ai<Ai+1A_i < A_{i+1}
  6. (26점) 수열 A=[A1,A2,⋯ ,AN]A = [A_1, A_2, \cdots, A_N]에 변화를 2020번 적용한 뒤에는, 변화를 추가로 적용해도 수열이 바뀌지 않는다.
  7. (32점) 추가 제약 조건 없음.

입력 형식

첫 줄에 두 정수 NN과 QQ가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

그다음 QQ개의 줄에 걸쳐, QQ개의 쿼리에 대한 정보가 주어진다. 각 줄에는 하나의 쿼리를 나타내는 세 정수 ll, rr, tt가 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄부터 QQ개의 줄에 걸쳐, QQ개의 쿼리에 대한 답을 출력한다. 입력에 주어진 순서대로, 쿼리마다 답을 한 줄에 하나씩 출력한다.

예제

예제 1

입력
5 5
5 1 3 2 4
1 5 1
1 5 2
1 4 1
2 5 1
1 5 5
출력
3
2
3
3
2

예제 2

입력
15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7
출력
11
8
6
4
3
2
2

예제 3

입력
10 10
9 6 4 1 8 2 3 5 7 10
1 10 1
1 10 2
1 10 5
1 9 3
2 10 2
2 10 4
3 8 1
3 8 2
1 5 4
4 8 3
출력
8
6
2
3
5
3
4
3
2
3

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.