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
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll MAXN = 200007;
ll hasz(ll x, ll y){
    return MAXN * x + y;
}

bool moze(int x, int y, const unordered_set<ll> &s){
    return (!s.count(hasz(x, y - 1)) and !s.count(hasz(x, y + 1))) || (!s.count(hasz(x - 1, y)) and !s.count(hasz(x + 1, y)));
}

int licz(unordered_set<ll> s){
    deque<ll> q;
    for(auto Hasz : s) if(moze(Hasz / MAXN, Hasz % MAXN, s)) q.push_back(Hasz);
    while(!q.empty()){
        ll u = q.front();
        q.pop_front();
        if(!s.count(u)) continue;
        s.erase(u);
        int x1 = u / MAXN;
        int x2 = u / MAXN;
        int x3 = u / MAXN + 1;
        int x4 = u / MAXN - 1;
        int y1 = u % MAXN + 1;
        int y2 = u % MAXN - 1;
        int y3 = u % MAXN;
        int y4 = u % MAXN;
        if(s.count(hasz(x1, y1)) and moze(x1, y1, s)) q.push_back(hasz(x1, y1));
        if(s.count(hasz(x2, y2)) and moze(x2, y2, s)) q.push_back(hasz(x2, y2));
        if(s.count(hasz(x3, y3)) and moze(x3, y3, s)) q.push_back(hasz(x3, y3));
        if(s.count(hasz(x4, y4)) and moze(x4, y4, s)) q.push_back(hasz(x4, y4));
    }
    return s.size();
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m, k, q;
    cin >> n >> m >> k >> q;
    unordered_set<ll> s;
    s.reserve(k + q + 7);
    for(int i = 0; i < k; i++){
        int x, y;
        cin >> x >> y;
        s.insert(hasz(x,y));
    }
    cout << s.size() - licz(s) << '\n';
    while(q--){
        int x, y;
        cin >> x >> y;
        if(s.count(hasz(x,y))) s.erase(hasz(x,y));
        else s.insert(hasz(x,y));
        cout << s.size() - licz(s) << '\n';
    }
}