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
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using namespace std;
const int maxn = 150 * 1000 + 5;
map<pi,int> mapa;
int nr = 1;
int kier[maxn][4],vis[maxn];
set<int> aktualne;
void odpowiedz(){
    vis[0] = 1;
    queue<int> Q;
    int licz = 0;
    for(auto y : aktualne){
        if(vis[y] == 1){continue;}
        if((kier[y][0] == 0 && kier[y][1] == 0) || (kier[y][2] == 0 && kier[y][3] == 0)){
            vis[y] = 1;
            Q.push(y);
            ++licz;
        }
    }
    while(!Q.empty()){
        auto x = Q.front();
        Q.pop();
        FOR(i,0,4){
            if(kier[x][i] != 0 && vis[kier[x][i]] == 0){
                int nowy = kier[x][i];
                if((vis[kier[nowy][0]] == 1 && vis[kier[nowy][1]] == 1) || (vis[kier[nowy][2]] == 1 && vis[kier[nowy][3]] == 1)){
                    vis[nowy] = 1;
                    Q.push(nowy);
                    ++licz;
                }
            }
        }
    }
    for(auto y : aktualne){
        vis[y] = 0;
    }
    cout<<licz <<"\n";
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,k,q;
    cin>>n >>m >>k >>q;
    vector<pi> V;
    FOR(i,0,k){
        int a,b;
        cin>>a >>b;
        mapa[{a,b}] = nr;
        V.pb({a,b});
        aktualne.insert(nr);
        ++nr;
    }
    FOR(i,0,V.size()){
        if(mapa.find({V[i].f + 1,V[i].s}) != mapa.end()){
            kier[i + 1][0] = mapa[{V[i].f + 1,V[i].s}];
        }
        if(mapa.find({V[i].f - 1,V[i].s}) != mapa.end()){
            kier[i + 1][1] = mapa[{V[i].f - 1,V[i].s}];
        }
        if(mapa.find({V[i].f,V[i].s + 1}) != mapa.end()){
            kier[i + 1][2] = mapa[{V[i].f,V[i].s + 1}];
        }
        if(mapa.find({V[i].f,V[i].s - 1}) != mapa.end()){
            kier[i + 1][3] = mapa[{V[i].f,V[i].s - 1}];
        }
    }
    odpowiedz();
    FOR(i,0,q){
        int a,b;
        cin>>a >>b;
        if(mapa[{a,b}] == 0){ //dodaj
            mapa[{a,b}] = nr;
            aktualne.insert(nr);
            if(mapa.find({a + 1,b}) != mapa.end()){
                kier[nr][0] = mapa[{a + 1,b}];
                kier[mapa[{a + 1,b}]][1] = nr;
            }
            if(mapa.find({a - 1,b}) != mapa.end()){
                kier[nr][1] = mapa[{a - 1,b}];
                kier[mapa[{a - 1,b}]][0] = nr;
            }
            if(mapa.find({a,b + 1}) != mapa.end()){
                kier[nr][2] = mapa[{a,b + 1}];
                kier[mapa[{a,b + 1}]][3] = nr;
            }
            if(mapa.find({a,b - 1}) != mapa.end()){
                kier[nr][3] = mapa[{a,b - 1}];
                kier[mapa[{a,b - 1}]][2] = nr;
            }
            ++nr;
        }else{ //odejmij
            int num = mapa[{a,b}];
            vis[num] = 1;
            aktualne.erase(num);
            mapa[{a,b}] = 0;
            if(kier[num][0] != 0){
                kier[kier[num][0]][1] = 0;
            }
            if(kier[num][1] != 0){
                kier[kier[num][1]][0] = 0;
            }
            if(kier[num][2] != 0){
                kier[kier[num][2]][3] = 0;
            }
            if(kier[num][3] != 0){
                kier[kier[num][3]][2] = 0;
            }
        }
        odpowiedz();
    }
}