원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
극솟값 제거
원제: 극솟값 제거
문제
서로 다른 정수로 이루어진 길이 의 수열 이 주어진다.
수열 에 대해, 다음 과정을 한 번의 변화라고 하자.
- 라고 하자. 각 정수 에 대하여, 를 만족할 때 를 제거할 원소라고 하자. 수열 에서 제거할 원소들을 모두 동시에 제거한 뒤, 남은 원소들을 순서를 유지하여 다시 붙인다.
예를 들어, 수열 에 변화를 번 적용하면 다음과 같이 변한다.
개의 쿼리가 주어진다. 각 쿼리는 세 정수 , , 로 표현할 수 있다. 각 쿼리 에 대하여, 수열 에 변화를 번 적용한 후, 이 수열에 남아 있는 원소의 개수를 구하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 수열 는 의 순열이다. 즉,
- 각 쿼리에 대하여,
- 각 쿼리에 대하여,
부분문제
- (6점) ; 각 쿼리에 대하여, 과 을 만족한다.
- (11점) 각 쿼리에 대하여, 과 을 만족한다.
- (6점) 각 쿼리에 대하여,
- (12점) 각 쿼리에 대하여,
- (7점) 어떤 정수 ()가 존재하여 다음 조건을 모두 만족한다.
- 정수 에 대하여
- 정수 에 대하여
- (26점) 수열 에 변화를 번 적용한 뒤에는, 변화를 추가로 적용해도 수열이 바뀌지 않는다.
- (32점) 추가 제약 조건 없음.
입력 형식
첫 줄에 두 정수 과 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
그다음 개의 줄에 걸쳐, 개의 쿼리에 대한 정보가 주어진다. 각 줄에는 하나의 쿼리를 나타내는 세 정수 , , 가 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄부터 개의 줄에 걸쳐, 개의 쿼리에 대한 답을 출력한다. 입력에 주어진 순서대로, 쿼리마다 답을 한 줄에 하나씩 출력한다.
예제
예제 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