문제
주식회사 김석표는 사업이 커짐에 따라 신규 채용을 하기로 결정했다.
회사의 사장 석표는 N명의 지원자를 대상으로 면접을 진행해 i번 지원자에게 A_i의 점수를 매겼다.
석표가 신입 사원들을 뽑게 되면, 지원 당시의 번호를 기준으로 그룹을 나눠 교육한다.
구체적으로, 두 지원자 a번과 b번 (a<b)은 a번과 b번 사이의 모든 지원자가 합격했을 경우 같은 그룹에 속한다.
석표는 회사를 위해 고민이 많다.
석표는 고민을 하면서 직원인 당신에게 두 가지 종류의 명령을 Q번 한다.
하나는 '점수가 B 이상인 직원을 모두 뽑으면 몇 그룹이 생기지?' 라는 질문이다.
다른 하나는 'C번 직원의 평가 점수를 D로 수정해줘.' 라는 지시이다.
사장님의 명령을 수행하고 승진의 기회를 노려보자!
입력
첫 줄에 N Q가 입력된다.
이후 N줄에 걸쳐 i번째 줄에 A_i가 입력된다.
그 다음 Q줄에 걸쳐 순서대로 줄마다 1 B 또는 2 C D의 형태로 명령이 주어진다.
1 B가 주어지면 B 이상의 점수를 받은 지원자를 모두 합격시킬 때 그룹의 수를 출력해야 한다.
2 C D가 주어지면 A_C의 값을 D로 변경해야 하며, 이 변화는 이후에도 계속 유지된다.
1 <= N, Q <= 200,000
1 <= A_i, B, D <= 1,000,000,000
1 <= C <= N
1 B 형태의 질문이 한 개 이상 들어온다.
출력
입력에서 1 B 꼴로 그룹의 수를 묻는 질문마다 한 줄에 하나씩 각 질문의 답을 출력하라.
예제 #1
5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3
2
1
2
예제 #2
7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17
0
1
3
3
2
예제 #3
10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16
2
1
0
출처
JOISC 2016
로그인해야 코드를 작성할 수 있어요.