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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <bits/stdc++.h>
using namespace std;

struct block {
    int x;
    int y;
//    int index;
    bool pickable = false;
    int urdl[4] = {0, 0, 0, 0};         //up, right, down, left - clockwise
    block(int X, int Y) { x = X; y = Y; };
};
struct allData {
    vector<block> graph;
    map<pair<int,int>, int> dict;           // (x,y)->index
    int total = 0;
    int pickable = 0;
    allData() {
        graph.emplace_back(0,0);
        graph[0].pickable = true;           // guard/noBlock IS pickable
                    //for proper indexing, bc map returns 0 by default (so we don't use index 0)
    }
};

inline int addToData(allData& all, int x, int y) {
                //add (x,y) to graph in all and do not check if it can be picked
    all.graph.emplace_back(x,y);
    int curIndex = (int)all.graph.size()-1;
    all.dict[{x,y}] = curIndex;
    block &curBlock = all.graph[curIndex];

    int ud[] = {1, 0, -1, 0};           //to check all four neighbours in a loop
    int rl[] = {0, 1, 0, -1};           //up and right -> 1, down and left -> -1
    for(int i=0; i<4; i++) {            //up, right, down, left - clockwise
        int checkIndex = all.dict[{x+ud[i], y+rl[i]}];
        if(checkIndex == 0)         //does not exist
            continue;
        //else -> connect
        curBlock.urdl[i] = checkIndex;
        all.graph[checkIndex].urdl[(i+2)&3] = curIndex;         //+2 modulo 4 - opposite side
    }
    return curIndex;
}

bool checkPickability(allData &all, block &cur) {
    return (all.graph[cur.urdl[0]].pickable && all.graph[cur.urdl[2]].pickable)
           || (all.graph[cur.urdl[1]].pickable && all.graph[cur.urdl[3]].pickable);
                //if either u&&d pickable or r&&l pickable
}
inline void prepare(allData& all) {
                //label all pickable blocks as pickable, set all.total and all.pickable
    queue<int> pickable;            //indexes in all.graph
    int size = (int)all.graph.size();
    all.total = size-1;
    all.pickable = 0;
    int pickCount = 0;
    for(int i=1; i<size; i++) {
        block &cur = all.graph[i];
        if(cur.pickable) {          //theoretical skip, won't happen if prepare is used as intended
            pickCount++;
            continue;
        }
        if(checkPickability(all, cur)) {
            cur.pickable = true;
            pickCount++;
            pickable.emplace(i);
        }
    }

    while(!pickable.empty()) {
        int index = pickable.front();
        pickable.pop();
        block &cur = all.graph[index];
        for(int i=0; i<4; i++) {            //up, right, down, left - clockwise
            block &checked = all.graph[cur.urdl[i]];
            if(checked.pickable)           //already pickable
                continue;
            //else -> wasn't pickable, but can be now (check what's behind it)
            if(all.graph[ checked.urdl[i] ].pickable) {         //if the one behind checked is pickable
                pickCount++;
                checked.pickable = true;
                pickable.emplace(cur.urdl[i]);          //add the checked one to the queue
            }
        }
    }
    all.pickable = pickCount;
}

inline void calculate(allData &all, int x, int y) {
            //return the number of blocks that are pickable AFTER current move
    int index = all.dict[{x,y}];
    if(index == 0) {            //add
        all.total++;
        index = addToData(all, x, y);           //added, now check if pickable
        queue<int> potential;           //those that may be blocked
        queue<int> clear;           //those that are pickable anyway -> for second bfs
        potential.emplace(index);
        while(!potential.empty()) {         //all in here have just been blocked
            int curIndex = potential.front();
            potential.pop();
            block &cur = all.graph[curIndex];
            if((cur.urdl[0] == 0 && cur.urdl[2] == 0) || (cur.urdl[1] == 0 && cur.urdl[3] == 0)) {
                cur.pickable = true;
                all.pickable++;
                clear.emplace(curIndex);
                continue;
            }
            //else -> not pickable right away, block neighbours
            for(int i=0; i<4; i++) {
                if(cur.urdl[i] != 0 && all.graph[cur.urdl[i]].pickable) {
                    all.graph[cur.urdl[i]].pickable = false;
                    all.pickable--;
                    potential.emplace(cur.urdl[i]);
                }
            }
        }
        //now check what can be cleared
        while(!clear.empty()) {
            int curIndex = clear.front();
            clear.pop();
            block &cur = all.graph[curIndex];
            for(int i=0; i<4; i++) {
                block &checked = all.graph[cur.urdl[i]];
                if(checkPickability(all, checked)) {            //pickable
                    if(checked.pickable)
                        continue;           //already pickable
                    checked.pickable = true;
                    all.pickable++;
                    clear.emplace(cur.urdl[i]);          //add the checked one to the queue
                }
            }
        }
    }
    else {          //remove
        block &cur = all.graph[index];
        all.total--;
        all.dict[{x,y}] = 0;            //remove from map
        queue<int> neighbourhood;
        for(int i=0; i<4; i++) {
            if(!all.graph[cur.urdl[i]].pickable) {
                neighbourhood.emplace(cur.urdl[i]);
            }
            all.graph[cur.urdl[i]].urdl[(i+2)&3] = 0;           //+2 modulo 4
                        //remove me from my neighbours adjacency lists
        }
        if(cur.pickable) {         //simple case, doesn't change much
            all.pickable--;
            return;
        }
        //else -> i was blocked
        while(!neighbourhood.empty()) {
            int checked = neighbourhood.front();
            block &cur2 = all.graph[checked];
            neighbourhood.pop();
            if(cur2.pickable) {           //skip
                continue;
            }
            //else -> blocked
            if(checkPickability(all, cur2)) {
                cur2.pickable = true;
                all.pickable++;
                for(int i=0; i<4; i++) {
                    if(!all.graph[cur2.urdl[i]].pickable) {          //neighbour not pickable (yet)
                        neighbourhood.emplace(cur2.urdl[i]);         //check if can be picked
                    }
                }
            }
            //else -> do nothing (blocked and can't be changed)
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, k, q;         //height, width, starting tiles, queries
    cin >> n >> m >> k >> q;
    allData all;

    int x, y;
    while(k--) {
        cin >> x >> y;
        addToData(all, x, y);
    }
    prepare(all);
    cout << all.pickable << "\n";

    while(q--) {            //from now on all.graph might not be coherent (invalid slots allowed)
        cin >> x >> y;
        calculate(all, x, y);
        cout << all.pickable << "\n";
    }
    return 0;
}