Полное решение: Давайте заметим, что если есть какое-то четное кол-во (-1), то в итоге все -1 превратятся в одну положительную единицу.

Поэтому посчитаем все такие (-1), и просто возьмем их кол-во по модулю 2.

Это и будет частью ответа. Дальше заметим, что если есть какое-то кол-во 0,

то с ними мы ничего не сделаем, а значит второй частью ответа просто будет кол-во 0. Выведем наш ответ, как cnt1%2+cnt0,

где cnt1 — кол-во -1, а cnt2 — кол-во 0.

Сложность: O(n)

Полное решение: Т.к нам нужно максимизировать наш ответ,

давайте просто возьмем самый максимальный элемент в пару со вторым максимальным, итд.

Для этого можно просто отсортировать массив.

Выведем наш ответ.

Сложность: O(nlogn)

Полное решение:

Давайте заметим, что если до требуемого k, нет какого-то числа, то нам не остается ничего,

как просто добавить это число, так же если f(k)!=0, где f(x) —

кол-во вхождений числа x в массив, то это число нужно заменить на какое-то другое тоже.

Дальше стоит заметить, что вышеуказанные операции могут пересекаться, тогда ответом будет max(cnt,f(k)), где cnt — кол-во таких чисел от 0 до k, что вхождении в массив у этих элементов равна 0, т.е f(x) == 0.

Выведем наш ответ.

Сложность: O(n)

Полное решение:

Допустим строка такая: ababaaba. Давайте просимулируем процесс для все b, для наглядности.

i = 2, нам нужно посчитать кол-во сдвигов слева и справа, т.к слева нет букв б, то берем справа.

bab = bba = 1 сдвиг.

bbaaab = bbbaaa — 3 сдвига.

Заметим, что для каждого b от 0 до і, число сдвигов до і это кол-во букв а от j до і, где j<i.

Также для каждого b от і до n, число сдвигов до n, это кол-во букв от і до j, где j>=i.

Тут можно заметить, что для каждого i, s[i] == 'b', сумма сдвигов считается как

(Lefta — Righta)*p[i]+((sump[n-1]-sump[i-1])-sump[i-1]),

где lefta — кол-во букв а от 0 до і-1,

а rigtha — кол-во букв а от і до n, p[i] — кол-во букв б от 0 до і-1.

Sump[i] — сумма всех p[i] таких индексов, что s[i]=='b'.

Для буквы а делаем точно также, только уже с другими префиксами. Для большей наглядности можете просмотреть мой код.

Сложность: O(n)

Полное решение:

Сперва вспомним один из самых важных лайфхаков связанное с работой на отрезках, а именно:

Чтобы найти ответ для отрезка l — r, можно найти ответ для r, и отнять от него ответ для l-1.

Теперь как использовать это для этой задачи? Давайте найдем кол-во отрезков с различными числами <=k, на отрезке от l — r, затем отнимем кол-во отрезков с различными числами <=k-1, на отрезке от l — r. Это и будет нашим ответом для данной задачи.

P.S: Ответ мы можем находить с помощью двух указателей/ sliding window. Для большей ясности можете просмотреть мой код.

Выведем наш ответ.

Сложность: O(n)*4