Учитывая сетку, m * n, где каждая ячейка может быть окрашена в зеленый или красный цвет, выведите количество подсеток, у которых все ячейки с одинаковым цветом красного со сложностью по времени лучше, чем m ^ 2 * n или m * n ^ 2.
Пример Сетка:
[[r, r, r, r],
[r, g, g, g],
[r, r, r, r]]
, где r представляет красный, а g представляет зеленый. Выходные данные должны быть 24 для всех подрешеток только с красной ячейкой (с).
Аналогичная проблема с кодом находится здесь: Количество подматриц, содержащих все нули
Однако, использование дерева сегментов в приведенном выше решении и утверждение «Как вы можно увидеть, добавим ли мы все эти числа, мы получим ответ для данной гистограммы. " не понятны мне. Может ли кто-нибудь объяснить мне любой алгоритм, который лучше, чем куби c?