$|x_i - X_j| + |y_i - Y_j| = \max(x_i - X_j + y_i - Y_j, -x_i + X_j + y_i - Y_j, x_i - X_j - y_i + Y_j, -x_i + X_j - y_i + Y_j)$, в аргументах максимума содержатся все $4$ способа раскрыть оба модуля. В каждом из $4$ выражений можно сгруппировать слагаемые, зависящие только от $i$ и только от $j$. Будем поддерживать максимумы для каждого из $4$ выражений для магазинов и для точек закупки. Тогда после каждого обновления достаточно перебрать сумму соответствующих максимумов по всем вариантам расставить знаки. Чтобы поддерживать эти максимумы, можно использовать set. Получаем решение за $O(n + q) \log (n + q))$ с большой константой.

Если константа оказалась слишком большой и решение не заходит, есть $2$ варианта её уменьшить. Первый - заменить set на priority queue с удалениями (помимо обычной кучи также хранить кучу del, куда добавлять удалённые элементы, тогда перед каждой операцией top() и empty() нужно сначала сделать операцию flush() --- пока top() в обеих кучах совпадает, удалить его из обеих куч). Второй вариант - сделать DCP offline, тогда можно просто хранить одно число для максимума.