Для первой группы тестов достаточно просто рассмотреть несколько вариантов вручную.

Для второй группы можно заметить, что $$$|c - a| + |c - b| = 2 \cdot |c - a|$$$. Т.к. $$$c$$$ мы можем выбирать сами, то достаточно просто выводить 0.

Для третьей группы достаточно просто перебирать $$$c$$$ от $$$1$$$ до $$$10^5$$$.

На полное решение можем построить числовую прямую, на которой найти, что минимальное значение выражения достигается при C, лежащем в диапазоне [$min(a, b), max(a, b)

Unable to parse markup [type=CF_MATHJAX]

Для решения первой группы тестов достаточно просто находить сумму `В лоб': для каждого запроса находим сумму на подматрице последовательно суммируя все её элементы. Асимптотика — $$$O(qnm)$$$.

На вторую группу тестов можно было написать решение, которое по заданным границам находит площадь прямоугольника. Несложно увидеть, что, раз матрица заполнена числами 1, то ответом именно такого вида.

На четвёртую группу тестов можно было написать одномерные префиксные суммы. Асимптотика — $$$O(q \cdot min(n, m))$$$.

На третью группу можно было написать двумерные префиксные суммы, но выводить просто p[i][j], где p — массив префиксных сумм. Для полного решения нужно было догадаться, что ответ равен p[rx][ry] — p[lx — 1][ry] — p[rx][ly — 1] + p[lx — 1][ly — 1]. Только нужно следить за выходом за границы массива. Асимптотика — $$$O(q)$$$

На первую группу тестов достаточно было просто симулировать игру вручную.

На вторую группу тестов достаточно написать рекурсивную реализацию игры. Асимптотика — $$$O(tnlogn)$$$

У многих сегодня упали даже полные решения на последней подгруппе. Это произошло потому, что количество выводимых чисел очень большое, а эти люди пользовались endl вместо $\backslash$n, который с каждым выводом замедлял программу.

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

2 способ полного решения:

Просчитаем ответ для каждого числа от 0 до 4 (0 — No, 1 — Yes):

0 1 0 1 1

Далее заметим, что для каждого следующего числа будем выводить 1, если оно чётное, либо 0 в противном случае. Почему это работает?

Всё достаточно просто. Если мы находимся в чётном числе, то мы просто отнимем 1. Таким образом противнику ничего не остаётся кроме того, чтобы отнять 1. Таким образом дойдём до числа 4, которое является выигрышным. Если же число нечётное, то теперь мы находимся в зеркальной ситуации и противник дойдёт до 4.

Для первой группы тестов рассмотрим два случая:

Если |p| = 1, s[0] = p[0], то ответ будет 1.

Иначе ответ будет 0.

Для второй группы тестов подсчитаем количество вхождений p[0] в s с помощью простого сохранения счётчика cnt.

Для третьей группы тестов можно рассмотреть два случая:

Если все символы в $$$p$$$ равны, то ответ будет $$$C^{|s|}_{|p|}$$$ по определению.

В любом ином случае ответ будет 0.

Для четвёртой группы можно было фиксировать s[i] и также рассматривать два случая:

Если s[i] = p[0], то к ответу нужно прибавить количество вхождений p[1] на суффиксе [i + 1, |s| — 1]. Количество вхождений можно было просчитать для каждого символа с помощью префиксных сумм.

Иначе к ответу ничего прибавлять не надо.

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

Напишем несложное ДП, где dp[i][j] — количество вхождений строки p[j..(|p| — 1)] в строку s[i..(|s| — 1)].

Теперь напишем формулу перехода:

Будем писать рекурсивную реализацию, поэтому далее под count(i, j) подразумевается подсчёт dp[i][j].

Тогда `отщипнём' от строки s i-й символ и прибавим к dp[i][j] count(i + 1, j).

Также нам нужно обрабатывать варианты, когда s[i] = p[j]. В нём мы просто `отщипнём' от строки s i-й символ, от от p j-й символ и прибавим к dp[i][j] count(i + 1, j + 1).

Какая база dp?

Если j == |p|, то мы нашли вхождение, то есть return 1.

Если же i == |s|, то мы не нашли его. то есть return 0.

Асимптотика — $$$O(|s| \cdot |p|)$$$

Заметим, что под кандидаты чисел подходят только квадраты простых чисел. Тогда переберём все простые числа до $$$\sqrt{n}$$$ и проверим, подходят ли они под неравенство $$$l \le cur^2 \le r$$$. Асимптотика — $$$O(\sqrt n loglog(\sqrt n ))$$$

В данной задаче я специально не ставил контртест на это решение, т.к. многие на этом контесте не знают логарифмов.

Мы можем просто посчитать префиксные произведения и перебирать индекс раздела.

Для того, чтобы решение прошло даже с контртестом, сделаем так: нам надо найти отрезок с максимальным значением. Тогда давайте возьмём логарифм произведения. Максимальный отрезок как и был максимальным, так и остался. Воспользуемся интересным свойством: логарифм произведения равен сумме логарифмов. Теперь мы уменьшили числа. Давайте с помощью этого метода логарифмирования найдём отрезок с максимальным значением и уже для исходного массива посчитаем ответ по заданному модулю.

Асимптотика: $$$O(n \cdot log(sum(a)))$$$