1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <unordered_set>
#include <queue>
using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)

struct Pair {
    int r, c;
    Pair(const int rr, const int cc) : r(rr), c(cc) {}
    Pair() : r(0), c(0) {}
    bool operator==(const Pair &other) const {
        return r == other.r && c == other.c;
    }
};

struct PairHash {
    size_t operator()(const Pair &p) const {
        return static_cast<size_t>(p.r) * 13131ULL + static_cast<size_t>(p.c);
    }
};

class AlgosiasProblem {
    int n{}, m{};
    unordered_set<Pair, PairHash> board;

    bool hasBlock(const unordered_set<Pair, PairHash>& S, const int r, const int c) const {
        if (r < 1 || r > n || c < 1 || c > m)
            return false;
        return (S.contains(Pair(r, c)));
    }

    bool canRemove(const unordered_set<Pair, PairHash>& S, const int r, const int c) const {
        bool hor = (!hasBlock(S, r, c - 1) && !hasBlock(S, r, c + 1));
        bool ver = (!hasBlock(S, r - 1, c) && !hasBlock(S, r + 1, c));
        return (hor || ver);
    }

    int simulateRemoval(const unordered_set<Pair, PairHash>& conf) const {
        unordered_set<Pair, PairHash> S = conf;
        queue<Pair> q;

        for (auto &b : S) {
            if (canRemove(S, b.r, b.c))
                q.push(b);
        }
        int removedCount = 0;

        int dr[4] = {0, 0, 1, -1};
        int dc[4] = {1, -1, 0, 0};

        while (!q.empty()) {
            Pair cur = q.front();
            q.pop();
            if (S.find(cur) == S.end()) continue;
            if (!canRemove(S, cur.r, cur.c))
                continue;

            S.erase(cur);
            removedCount++;

            REP(i, 4) {
                const int nr = cur.r + dr[i];
                if (int nc = cur.c + dc[i]; hasBlock(S, nr, nc))
                    q.emplace(nr, nc);
            }
            REP(i, 4) {
                int nr = cur.r + 2 * dr[i];
                int nc = cur.c + 2 * dc[i];
                if (hasBlock(S, nr, nc))
                    q.emplace(nr, nc);
            }
        }
        return removedCount;
    }

public:
    void resolve() {

        int k, q;
        cin >> n >> m >> k >> q;
        board.clear();
        REP(i, k) {
            int r, c;
            cin >> r >> c;
            board.insert(Pair(r, c));
        }

        cout << simulateRemoval(board) << endl;

       REP(i, q) {
            int r, c;
            cin >> r >> c;

            if (Pair cur(r, c); board.contains(cur))
                board.erase(cur);
            else
                board.insert(cur);
            cout << simulateRemoval(board) << endl;
        }
    }
};

int main(){
    AlgosiasProblem solver;
    solver.resolve();
    return 0;
}