Разбор раунда #907

Это неофициальный разбор от @algo_easy. Обязательно подписывайтесь на тг-канал @algo_easy, там будет много интересного!!!

Если что-то непонятно, напишите @algo_admin

Ссылка на раунд: https://codeforces.com/contest/1891

Нажмите на нужную задачу:
Задача A.
Задача B.
Задача C.
Задача D.
Задача E(скоро).
БОНУС! Задача F.

Задача A

Факт/краткий разбор: Вы можете вычитать сколько угодно раз. Но у вас есть отрезки, 1..1, 2..2, 3..4, 5...8, 9...16 и т д. То есть между 2^(m-1) и 2^m. И в этих отрезках вы никак не можете отсортировать числа. Надо проверить неубывание в них.

Полный разбор: Выпишем все доступные m. Поймем, что в неубывающем порядке -> надо сделать a1<=a2<=a3...<=an. Тогда очевидно, что выгодно сначала для m=1 сделать много операций, для m=2 и т д. Можно просто сказать, что давайте сделаем INF операций для текущего m. И просто проверим, что 2^m<=n и для всех от 1...2^m вычтем INF. INF - это очень большое число, часто ставят 10^9 или 10^18.

Задача B

Факт/Кратко: Заметьте, что когда число делилось на 2^x и пришел запрос на x, это число больше никогда не будет делиться на 2^x. Просто из-за того, что прибавим 2^(x-1), уже не делится. А дальше мы будем всегда прибавлять еще меньшие степени. Но есть факт, что 1+2+...2^(n-1)=2^n-1<2^n. Тогда сохраним только "интересные" изменения. Это x[1]>x[i1]>x[i2]>x[i3]... Этих изменений очевидно не более x[1], то есть 30. А дальше можно пробежаться по каждому числу и отдельно для него сделать все изменения. Асимптотика O(n*30).

Полный разбор: прочитайте краткий разбор. Тут будут уточнения. Что такое интересное изменение? Это минимальное изменение на префиксе. Коротко говоря, x[i] - интересное изменение, если x[i]<x[1], x[i]<x[2]...x[i]<x[i-1]. Почему интересуют только интересные изменения? Из факта. Пусть мы считаем, что x[i] что-то изменит, но само оно >=x[j], что j<i. Но тогда из самый первых строчек из краткого разбора видно, что тогда никакие числа не делятся на 2^x[i] в момент i, потому что они изменились в момент j. Как считать интересные изменения? С помощью префиксных минимумов или как стек.

Задача C

Кратко: Хочется сделать жадник.

Полный разбор: Отсортируем числа. Посмотрим на сумму чисел sum. Тогда посмотрим на sum/2 округленное вверх. Заметим, что такое количество операций(то есть sum) мы точно сделаем. Просто из-за того, что надо перезагружать комбо, само оно не накопится)
На самом деле, пусть n=2*k или 2*k+1 в зависимости от четности. Тогда если сделаем первых операций(первого типа) меньше, чем sum/2 округленное вниз(то есть меньше k или меньше k+1 в зависимости от четности), то самого комба тоже не более чем это число будет(то есть тоже меньше k/k+1). А сумма количества первого типа операций+комба=сколько убили монстров(легкий факт, проверьте на листочке). Доказали факт. То есть снизу нам это точно нужно. Но при этом сверху тоже количество первого типа хватает(потому что sum2*2>=n, где sum2 = Sum/2 округленное вверх). Давайте тогда ходить и набирать комбу на первых нескольких чисел(пока sum2>0) и сливать эту комбу на суффиксе массива, мы же отсортировали числа -> нам так выгодно. Тогда ответ выглядит как sum2+количество ненулевых чисел после того, как мы прошлись по всему префиксу.

Задача D

Кратко: всего различных логарифмов чисел до 10^18 не более 60. Каждое f(x) выражается на каком-то отрезке. Возьмем отрезок и он тоже делится на свои отрезки. Утверждается, что таких отрезков немного.

Полный разбор: Различных логарифмов не больше 60, потому что 2^60>10^18. Тогда нам бы хотелось разбить все числа от 1...10^18 на отрезки в которых мы знаем, что g(x) не меняется. Я утверждаю, что таких отрезков мало(проверите на компе, когда напишите код). Как это сделать? Вы перебираете от 1...60 - различные логарифмы(пусть будет x). Тогда для конкретного x вы знаете, что этот x отвечает за отрезок 2^x...(2^(x+1) - 1). Пусть это L, R. И перебирайте все степени x^1, x^2...x^k, главное аккуратно и не вылететь за long long. И пусть L2, R2 - это отрезок для какого-то j, что он отвечает за отрезок x^j .... (x^(j+1) - 1). Надо пересечь эти два отрезка. Обычный прием: сказать, что пусть L=max(L, L2), R=min(R, R2). Можете убедиться на бумаге, что это правда. Все, теперь есть L, R и вы знаете, что на нем для всех L<=i<=R g(i)=j. Сохраните в условный вектор и ответьте на каждый запрос.

БОНУС! Задача F.

Внимание: Надо знать что такое Дерево Отрезков(сокращенно ДО) или Дерево Фенвика(ДФ). И что такое дфс.

Полный разбор: Давайте сохранять для каждой вершины момент времени t, когда она появилась в дереве. Аналогично для каждого вершины сохраняем все пары {time, x} - прибавление x в момент time на всем поддереве. Тогда пройдемся по всем запросам и сохраним нужные значения. Запустим dfs из первой вершины.
Когда мы зашли в вершину u, посмотрим на все её пары {time, x}. И в ДО/ДФ в точке time сделаем +x. Но когда будем выходить из этой вершины сделаем аналогично в точке time -x. Что тогда? На вершину u очевидно влияют все точки tq...q+1, где tq - время добавления вершины u в дерево. Точки 1...tq-1 не влияют ведь эти запросы на поддереве были сделаны раньше, чем вершина u появилась в дереве.

Почему работает? Просто из-за того, что когда сделали в вершине u в точке time +=x. Этот +=x будет влиять на все поддерево u, ведь мы дальше вниз пойдем. А при выходе из u мы сделаем -=x в точке time. То есть на все остальные вершины не влияем.