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
#include <cstdio>
#include <algorithm>
#include <vector>

const int max_n = 5000;
const int max_m = 300010;

int n, m, q;

std::vector<std::pair<int, int>> CCO[max_n];
std::vector<std::pair<int, int>> CCC[max_n];

int G[max_n][max_n];
int A[max_n];
int R[max_n];
int C[max_n];

void xor_range(int a, int b) {
    for (int i = a; i <= b; ++i) {
        A[i] = A[i] ^ 1;
    }
}


void max_matching() {
/*
    while (true) {
        ++vis;
        bool found = false;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (G[i][j] == 1 && M[i][j][0] == -1 && D[i][j] < vis && dfs(i, j)) {
                    ++matching;
                    found = true;
                }
            }
            if (found) break;
        }
        if (!found) break;        
    }
//    printf("MAX MATCHING=%d\n", matching);
    printf("%d\n", matching);
*/
    long long sum_1 = 0;
    for (int i = 1; i <= n; ++i) {
        C[i] = R[i] = 0;
        for (int j = 1; j <= n; ++j) {
            C[i] += G[i][j] == 1;
            R[i] += G[j][i] == 1;
            sum_1 += G[i][j] == 1;
        }
    }
    std::sort(C + 1, C + n + 1);
    std::sort(R + 1, R + n + 1);

    // zeroes
    long long sum_c = 0;
    long long max_miss0 = 0;
    for (int i = 1; i <= n; ++i) {
        if (n - C[i] < i) break;
        long long sum_r = 0;
        sum_c += C[i];
        for (int j = 1; j <= n; ++j) {
            if (n - R[j] < j) break;
            sum_r += R[j];
            max_miss0 = std::max(max_miss0, i * j - sum_r - sum_c);
        }
    }
    sum_c = 0;
    long long max_miss1 = 0;
    for (int i = 1; i <= n; ++i) {
        if (C[n - i + 1] < i) break;
        long long sum_r = 0;
        sum_c += n - C[n - i + 1];
        for (int j = 1; j <= n; ++j) {
            if (R[n - j + 1] < j) break;
            sum_r += n - R[n - j + 1];
            max_miss1 = std::max(max_miss1, i * j - sum_r - sum_c);
        }
    }
//    printf("%lld %lld %lld\n", sum_1, max_miss0, max_miss1);
    printf ("%lld\n", std::min(sum_1 - max_miss1, ((long long)(n) * n) - sum_1 - max_miss0));
//    return 0;


/*
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (M[i][j][0] == -1) printf("%d", G[i][j]);
            else printf("X");
        }
        printf("\n");
    }
*/
}

int main() {
    scanf ("%d %d %d", &n, &m, &q);
    for (int i = 0; i < m; ++i) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        CCO[x1].push_back(std::make_pair(y1, y2));
        CCC[x2].push_back(std::make_pair(y1, y2));
    }

    for (int i = 1; i <= n; ++i) A[i] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < CCO[i].size(); ++j) {
            xor_range(CCO[i][j].first, CCO[i][j].second);
        }
        for (int j = 1; j <= n; ++j) G[i][j] = A[j];
        for (int j = 0; j < CCC[i].size(); ++j) {
            xor_range(CCC[i][j].first, CCC[i][j].second);
        }
    }
    max_matching(); 


    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        G[x][y] = 1 ^ G[x][y];
        max_matching();
    }

    return 0;
}