다이아몬드 IV\(1\)부터 \(N\)까지의 정수가 각각 정확히 한 번씩 나타나는 순열 \(A = [A_1, A_2, \cdots, A_N]\)이 주어진다.
길이가 \(K\)인 수열 \(B = [B_1, B_2, \cdots, B_K]\)에 대한 변화를 다음과 같이 정의한다.
- 먼저 조건 \(2 \le i \le K-1\)을 만족하는 모든 내부 원소 \(B_i\) 중에서, \(B_{i-1} > B_i\)이고 \(B_i < B_{i+1}\)인 것, 즉 극솟값(양옆의 원소가 모두 자신보다 큰 원소)을 모두 표시한다.
- 그런 다음, 표시된 원소들을 동시에 모두 제거하고, 남은 원소들을 원래의 순서를 유지하면서 이어 붙인다.
수열의 양 끝 원소 \(B_1\)과 \(B_K\)는 (내부 원소가 아니므로) 어떤 경우에도 제거되지 않는다.
예를 들어, 수열 \([5, 1, 3, 2, 4]\)에 변화를 반복해서 가하면 다음과 같이 바뀐다.
$$ [5, 1, 3, 2, 4] \to [5, 3, 4] \to [5, 4] \to [5, 4] $$
첫 번째 변화에서는 \(1\)(양옆이 \(5, 3\))과 \(2\)(양옆이 \(3, 4\))가 동시에 극솟값이므로 함께 제거되어 \([5, 3, 4]\)가 된다. 두 번째 변화에서는 \(3\)(양옆이 \(5, 4\))이 제거되어 \([5, 4]\)가 되고, 그 뒤로는 더 이상 변하지 않는다.
이제 \(Q\)개의 질의가 주어진다. 각 질의는 세 정수 \(l, r, t\)로 이루어진다. 각 질의에 대하여, 수열 \(A\)의 부분수열 \([A_l, A_{l+1}, \cdots, A_r]\)을 택한 뒤 이 수열에 변화를 정확히 \(t\)번 가했을 때, 남아 있는 원소의 개수를 구하여라.
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 200{,}000\)
- \(1 \le Q \le 200{,}000\)
- 수열 \(A\)는 \(1, 2, \cdots, N\)의 순열이다. 즉, \(\{A_1, A_2, \cdots, A_N\} = \{1, 2, \cdots, N\}\)이다.
- 각 질의에 대하여 \(1 \le l \le r \le N\)이고 \(1 \le t \le N\)이다.
첫 줄에 두 정수 \(N\)과 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 순열을 이루는 \(N\)개의 정수 \(A_1, A_2, \cdots, A_N\)이 공백으로 구분되어 주어진다.
이어지는 \(Q\)개의 줄에 각 질의를 나타내는 세 정수 \(l, r, t\)가 공백으로 구분되어 주어진다.
각 질의에 대하여, 부분수열 \([A_l, \cdots, A_r]\)에 변화를 \(t\)번 가한 뒤 남아 있는 원소의 개수를 한 줄에 하나씩 차례대로 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 6점 | \(N \le 5{,}000\)이고, 모든 질의에서 \(l = 1\), \(r = N\)이다. |
Subtask 2 | 11점 | 모든 질의에서 \(l = 1\), \(r = N\)이다. |
Subtask 3 | 6점 | 모든 질의에서 \(t = 1\)이다. |
Subtask 4 | 12점 | 모든 질의에서 \(t = N\)이다. |
Subtask 5 | 7점 | 수열 \(A\)는 골짜기 모양이다. 즉, 어떤 \(p\)가 존재하여 \(A_1 > A_2 > \cdots > A_p\)이고 \(A_p < A_{p+1} < \cdots < A_N\)이다. |
Subtask 6 | 26점 | 수열 \(A\) 전체에 변화를 \(20\)번 적용하면 그 뒤로는 더 이상 변하지 않는다. |
Subtask 7 | 32점 | 추가적인 제약 조건이 없다. |
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
첫 번째 질의는 \([5, 1, 3, 2, 4]\)에 변화를 \(1\)번 가한 것으로, 결과는 \([5, 3, 4]\)이므로 \(3\)이다.
두 번째 질의는 같은 수열에 변화를 \(2\)번 가한 것으로, 결과는 \([5, 4]\)이므로 \(2\)이다.
세 번째 질의는 \([5, 1, 3, 2]\)에 변화를 \(1\)번 가한 것이다. \(1\)만 극솟값이므로 \([5, 3, 2]\)가 되어 \(3\)이다.
네 번째 질의는 \([1, 3, 2, 4]\)에 변화를 \(1\)번 가한 것이다. \(2\)만 극솟값이므로 \([1, 3, 4]\)가 되어 \(3\)이다.
다섯 번째 질의는 \([5, 1, 3, 2, 4]\)에 변화를 \(5\)번 가한 것으로, \([5, 4]\)에서 안정되므로 \(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
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