건초 더미 추측

시간 제한1초메모리 제한128 MB

요약

모든 값이 서로 다른 배열에서 구간 최솟값 질의가 주어질 때, 답들이 서로 모순되게 만드는 가장 이른 질의를 찾는다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 정렬, 유니온 파인드, 구현
정답자: 아직 제출이 없습니다

문제

숨겨진 건초 더미 배열이 다음과 같이 준비되어 있습니다. 더미는 모두 $N$ 개이며( $1 \le N \le 1{,}000{,}000$ ), $1$ 번부터 $N$ 번까지 번호가 매겨져 있습니다. 각 더미에 쌓인 건초 다발의 수는 서로 모두 다르며, 그 값은 $1$ 이상 $1{,}000{,}000{,}000$ 이하의 정수입니다.

더미를 직접 볼 수는 없고, 대신 다음과 같은 형태의 질문을 $Q$ 개 ( $1 \le Q \le 25{,}000$ ) 던집니다.

$Q_l$ 번부터 $Q_h$ 번까지의 더미 중에서 ( $1 \le Q_l \le Q_h \le N$ ), 건초 다발이 가장 적은 더미에는 몇 다발이 쌓여 있나요?

각 질문에는 정수 $A$ 하나로 답이 주어집니다. 이 답들은 항상 참이라는 보장이 없어서, 서로 모순되는 답이 섞여 있을 수 있습니다.

$Q$ 개의 답이 동시에 모두 참일 수 있는지, 즉 모든 답과 일치하는 더미 배열이 하나라도 존재하는지 판정하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $Q$ .
둘째 줄부터 $Q+1$ 째 줄까지: 각 줄에 공백으로 구분된 세 정수 $Q_l$ , $Q_h$ , $A$ 가 주어집니다. 이는 $Q_l$ 번부터 $Q_h$ 번까지의 더미에 대한 질문과 그 답 $A$ 를 나타냅니다.

출력

첫째 줄: 모든 답이 서로 모순되지 않으면(모든 $Q$ 개의 답과 일치하는 유효한 더미 배열이 존재하면) $0$ 을 출력합니다. 그렇지 않으면, 앞서 주어진 답들과 처음으로 모순을 일으키는 답의 순서를 $1$ 부터 $Q$ 까지의 번호로 출력합니다.

힌트

예시에서 세 번째 질문(“3 12 8”)이 앞선 답들과 처음으로 충돌합니다. 처음 두 답과, 모든 더미의 건초 다발 수가 서로 다르다는 사실로부터 $5$ 번부터 $10$ 번 더미 중 정확히 하나가 $7$ 다발을 가져야 함을 알 수 있습니다. 그러면 $7$ 다발짜리 더미가 $3$ 번부터 $12$ 번 구간 안에 들어가는데, 이 구간의 최솟값은 $8$ 이라고 답했으므로 모순이 발생합니다.

예제3

예제 1
입력
```
20 4
1 10 7
5 19 7
3 12 8
11 15 12
```
예상 출력
```
3
```
예제 2
입력
```
5 1
1 5 3
```
예상 출력
```
0
```
예제 3
입력
```
5 2
1 5 3
1 5 4
```
예상 출력
```
2
```