Как решать это? Как быстро удалять первый элемент и считать композицию?
1 лайк
Ну для начала стоит обратить внимание на сайт на котором данная задача находится. Library checker в основном сделан для того чтобы проверять работоспособность написанных алгоритмов/структур данных. Соответственно прямо в задаче есть ссылка на код решения.
Если забыть про факт выше то решать задачу можно так:
Второй запрос требует посчитать v(x) = f_n(f_{n-1}(...(f_1(x))...)), где x известно.
Давай научимся считать g(x) = f_1(f_{2}(...(f_n(x))...)). Сделаем это просто для удобства. (Теперь мы добавляем в начало и удаляем с конца)
Мы знаем что f_i = a_i * x + b_i.
Давай обозначим новый массив p, p_0 = 1, p_i = \prod\limits_{j=1}^{i} a_{j} = p_{i-1} * a_i.
Тогда g(x) = p_n * x + p_{n-1} * b_n + ... + p_1*b_2 + b_1 = p_n * x + \sum\limits_{i=0}^{n - 1}p_i * b_{i+1}.
Заметим что g(x) это функция вида k * x + c, где k = p_n, а c = \sum\limits_{i=0}^{n - 1}p_i * b_{i+1}.
Теперь задача сводится лишь к поддержанию этих значений k и c.
Поддерживать k мы можем в тупую применяя умножение и деление по модулю.
Поддерживать c мы можем так :
-
Удаление с конца, делаем в тупую. Для b_1 множителем так и останется p_0, для b_2 множителем так и останeтся p_1, …, для $b_{n-1} множителем так и останется p_{n-2}. Мы знаем что p_i и b_i (i < n) не изменятся. Значит единственное что нам нужно сделать это отнять b_n * p_{n-1}.
-
Добавление в начало (A, D). Все p_i и b_i сдвинутся направо, также каждый из прошлых p_i будет умножено на добавленное значение(обозначим его как A). Мы знаем что нам нужно считать только значение c, как повлияет это добавление на значение c? Очевидно что все прошлые пары b_i * p_{i-1} умножатся на A, также в сумму добавится значение D, тогда новое значение c будет c * A + D
Ну заметим что поддерживать массив p в реализации нам и не нужно. Действия теперь имеют такой вид:
Удаление: k' = \frac{k}{a_n}, c' = c - b_n * \frac{k}{a_n}, и удалим с конца a_n, b_n.
Добавление: k' = A * k, c' = A * c + D, и добавим в начало A, D.
Вывод: k * x + c.
Можем туп симулировать деком всё.
В решении выше могут быть некоторые косяки, но в целом идея такая.
9 лайков