Будем отвечать на запросы в обратном порядке. Для начала, будем рассматривать рамку как не более чем 4 полоски 1 × x или y × 1. Так как отвечаем мы на запросы в обратном порядке, полоски не добавляются, а удаляются. Что происходит при удалении полоски?
При удалении полоски некоторые непораженные области объединяются. А именно, если у нас есть полоска (x1, y1), (x2, y2), то объединиться могут только клетки в области (x1 - 1, y1 - 1), (x2 + 1, y2 + 1) (так как (x1, y1), (x2, y2) — полоска, то эта область размера не больше, чем 3 × x или y × 3. Используя СНМ (систему непересекающихся множеств) мы можем объединить все непораженные области за O(max(n, m)).
Итоговая асимптотика: O(q·max(n, m)).