Задача №113563. Ложь, наглая ложь и статистика
В распоряжении агрономического комбината «Олег и ко» находится n полей, пронумерованных от 1 до n . Для каждого поля определена его урожайность a i ≤ 10 9 — сколько килограмм винограда можно собрать с этого поля за год.
В связи с трудной экономической ситуацией руководству фирмы приходится принимать решительные (хоть и не совсем честные) меры по повышению стоимости акций предприятия. Руководство знает, что стоимость акций равна среднему арифметическому урожайностей полей, принадлежащих комбинату. Но эта величина может быть очень маленькой, поэтому руководство приняло решение сообщать при регистрации не обо всех полях, а лишь о каком-то множестве полей с последовательными индексами. Кроме того, некоторые поля не отвечают высоким стандартам производства винограда, поэтому регистрировать их нельзя (иначе фирму могут закрыть). Однако все знают, что у комбината более одного поля, поэтому регистрация одного поля будет выглядеть подозрительно, и, поэтому, директор всегда будет регистрировать не менее двух полей.
Вам необходимо помочь руководству фирмы и ответить на q запросов. Запросы могут быть одного из двух видов:
1 l r x — урожайность полей с номерами от l до r увеличиласть на x ( 1 ≤ x ≤ 10 9 ).
2 l r — предположим, разрешено регистрировать поля с номерами от l до r ( 1 ≤ l < r ≤ n ). Какой максимальной прибыли может добиться директор при правильном выборе полей, которые он будет регистрировать?
В первой строке входного файла задано 2 целых числа n и q — число полей у комбината и число запросов соответсвтенно.
Во второй строке задано n целых чисел a i ( 1 ≤ a i ≤ 10 9 ) через пробел — изначальные урожайности полей.
В следующих q строках заданы запросы в формате, описанном выше.
Для каждого запроса второго типа выведите вещественное число в отдельной строке — ответ на задачу. Ваш ответ будет считаться корректным если абсолютная или относительная погрешность не превосходит 10 - 4 .
n , q ≤ 100 — 15 баллов.
n , q ≤ 1000 — 50 баллов.
n , q ≤ 5·10 5 — 100 баллов.
3 3 2 1 2 2 1 3 1 2 2 4 2 1 3
1.66667 3.50000