Jungol

최근 해수면 상승으로 팽수의 고향 남극은 바닷물에 잠겨 소멸될 위기에 놓였다.

팽수는 슬픔에 잠겼지만, 남극의 위기를 제대로 확인하기 위해 해수면 높이에 따른 상태를 알고 싶어졌다.

남극 해안의 높이은 N개의 숫자 h_1,h_2,\cdots,h_N으로 나타낸다. 여기서 i번째 숫자는 i번째 구역의 해안 높이를 의미한다.

팽수는 Q개의 질문이 있다. i번째 질문은 다음과 같다:

만약 해수면이 x_i미터 만큼 상승한다면, l_i지점부터 r_i지점까지 섬이 몇 개가 되는가?

왼쪽 그림은 첫 번째 예제의 첫 번째 질문에 대한 결과이며, 오른쪽 그림은 두 번째 예제의 두 번째 질문에 대한 결과이다. 왼쪽 그림에서 섬은 [2,2], [4,5] 이며, 오른쪽 그림에서 섬은 [1,1], [4,4], [8,8], [10,10] 이다.

섬의 정의는 모든 h_i가 해수면보다 높은 연속된 구역으로 정의되며, 초기 상태는 해수면이 0미터이다.

입력

첫 번째 줄에 2개의 정수인 구역의 수 N과 질문의 수 Q가 공백을 구분으로 주어진다. (1 \le N,Q \le 2 \cdot 10^5)

두 번째 줄에 N개의 정수 h_1, h_2, \cdots, h_N (0 \le h_i \le 10^9)가 공백을 구분으로 주어진다.

그 다음 Q개의 줄에 걸쳐 3개의 정수 l_i, r_i,x_i (1 \le l_i \le r_i \le n, 0 \le x_i \le 10^9 )가 각 줄에 주어진다. 이는 i번째 질문을 의미한다.

출력

i번 줄에 i번째 질문에 대한 답을 출력한다. 모든 질문은 다른 질문과 독립적이다.

부분문제

번호	점수	조건
#1	10점	n,q \le 2 \cdot 10^3
#2	18점	모든 i=1,2, \cdots ,Q에 대해 l_i=1, r_i=n 이다.
#3	18점	h_1 \ge h_2 \ge \cdots \ge h_p i h_p \le h_{p+1} \le \cdots \le h_N 를 만족하는 p가 존재한다. (1 \le p \le N)
#4	54점	추가 제약 조건 없음.

예제1

첫 번째 질문은 2개의 섬이 구간 [2,2], [4,5]에 나타난다. (본문의 이미지 왼쪽 참고)

두 번째 질문은 1개의 섬이 구간 [5,5]에 나타난다.

세 번째 질문은 완전히 잠기기에 섬이 없다.

예제2

첫 번째 질문은 2개의 섬이 [3,5], [8,9]에 나타난다.

두 번째 질문은 4개의 섬이 [1,1], [4,4], [8,8], [10,10]에 나타난다. (본문의 이미지 오른쪽 참고)

세 번째 질문은 3개의 섬이 [1,1], [3,4], [8,10]에 나타난다.

출처

COCI 2023/2024 Contest #2 5번

남극 소멸 2초 512MB