Задача №3391. Обратная задача для RMQ
Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии
от классической постановки задачи, где по заданным исходным данным \(D\) требуется решить некоторую оптимизационную задачу \(P\), в обратной задаче по заданной задаче \(P\) и результату вычисления
\(R\) требуется подобрать исходные данные \(D\), на которых достигается этот результат. В этой задаче
вам предлагается решить обратную задачу к задаче о минимуме на отрезке (range minimum query,
RMQ).
Пусть задан массив \(a[1..n]\). Ответ на запрос о минимуме на отрезке \(Q(i, j)\) — это минимальное
среди значений \(a[i]\), ..., \(a[j]\). Вам дано \(n\) и последовательность запросов о минимуме на отрезке с
ответами. Восстановите исходный массив \(a\).
Первая строка входного файла содержит \(n\) — размер массива, и \(m\) — количество запросов (\(1 \leq n, m \leq 100000\)). Следующие \(m\) строк содержат по три целых числа: числа \(i\), \(j\) и \(q\) означают, что \(Q(i, j) = q\) (\(1 \leq i \leq j \leq n\), \(-2^{31} \leq q \leq 2^{31} - 1\)).
Если входные данные несовместны, то есть искомого массива a не существует, выведите
"inconsistent" на первой строке выходного файла.
В противном случае выведите “consistent” на первой строке выходного файла. Вторая строка
должна содержать сам массив. Элементы массива должны быть целыми числами между \(2^{31}\) и \(2^{31}-1\). Если решений несколько, выведите любое.
Баллы за эту задачу будут начислены только если решение проходит все тесты
3 2 1 2 1 2 3 2
consistent 1 2 2
3 3 1 2 1 1 1 2 2 3 2
inconsistent