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
//Sylwia Sapkowska 
#include <bits/stdc++.h> 
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
typedef pair<int, int> T;

void solve(){
    int n, m; cin >> n >> m;
    int k, q; cin >> k >> q;
    vector<T>p(k), que(q);
    for (auto &[x, y]: p) cin >> x >> y;
    for (auto &[x, y]: que) cin >> x >> y;
    vector<T>s;
    for (auto x: p) s.emplace_back(x);
    for (auto x: que) s.emplace_back(x);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    vector<int>X = {-1, 1, 0, 0};
    vector<int>Y = {0, 0, 1, -1};
    int N = (int)s.size();
    vector<bool>active(N+1);
    auto get = [&](T x){
        return (int)(lower_bound(s.begin(), s.end(), x)-s.begin());
    };
    for (auto x: p){
        int i = get(x);
        active[i] = 1;
    }
    vector<vector<int>>neigh(N);
    for (int i = 0; i<N; i++){
        for (int ck = 0; ck < 4; ck++){
            T ss = {s[i].first+X[ck], s[i].second+Y[ck]};
            int id = get(ss);
            if (id < (int)s.size() && s[id] == ss){
                neigh[i].emplace_back(id);
            } else {
                neigh[i].emplace_back(N);
            }
        }
    }
    vector<bool>vis(N);
    auto answer = [&](){
        queue<int>qq;
        vis.assign(N, 0);
        for (int i = 0; i<N; i++){
            if (!active[i]) continue;
            // debug(s[i], neigh[i]);
            if ((!active[neigh[i][0]] && !active[neigh[i][1]]) || (!active[neigh[i][2]] && !active[neigh[i][3]])) {
                qq.push(i);
                // debug(s[i]);
                vis[i] = 1;
            }
        }
        int ans = 0;
        while ((int)qq.size()){
            auto i = qq.front();qq.pop();
            // debug(s[i]);
            ans++;
            for (auto j: neigh[i]){
                if (j == N || vis[j] || !active[j]) continue;
                //nieaktywny lub odwiedzony
                bool left = (!active[neigh[j][0]] || vis[neigh[j][0]]);
                bool right = (!active[neigh[j][1]] || vis[neigh[j][1]]);
                if (left && right){
                    vis[j] = 1;
                    qq.push(j);
                    continue;
                }
                left = (!active[neigh[j][2]] || vis[neigh[j][2]]);
                right = (!active[neigh[j][3]] || vis[neigh[j][3]]);
                if (left && right){
                    vis[j] = 1;
                    qq.push(j);
                }
            }
        }
        cout << ans << "\n";
    };
    answer();
    for (auto punkt: que){
        int i = get(punkt);
        active[i] = 1-active[i];
        answer();
    }
}
 
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}