Почти то, что вам нужно, называется поиск мостов — ребер, удаление которых делает граф(в частности компоненту связности) несвязным.
Почитать об этом можно тут.

Заведите второй массив, в котором, при записи на k-ый день, прибавляйте единичку на отрезке [k-n;k+n]. Теперь ваша задача свелась к проверке того, что значение в k-ой ячейке второго массива не больше m-1. Осталось научиться быстро прибавлять на отрезке и запрашивать значение k-го элемента.
Один из вариантов - дерево отрезков. Умеет выполнять операции прибавления на отрезке и запроса суммы на отрезке за O(log(n)).

И да, для вашей исходной, а не обобщенной, задачи реализация моего решения не прибавит скорости.