强迫症最喜欢的一集

建议了解知识点：哈希(hash), 集合(set)

哈希一般用来把一堆数字或一个字符串转化成一个数字，用于快速判断是否存在。这个转化后的数字我一般称之为哈希值。在哈希值较大的时候（>1e18）时，我们可以把这个数字对一个大整数 MOD 取余。但是此时可能会出现取余完后两个不同哈希值的内容取余结果一样的情况，也就是哈希冲突，但是在随机数据下概率较低。

本题将 $(x_1, y_1) \rightarrow (x_2,y_2)$ 的一条边用一个数字 $H$ 表示, $H = x_1 + C \cdot y_1 + C^2 \cdot x_2 + C^3 \cdot y_2$ （在代码中我的C为514）。由于 $x_1, y_1, x_2 ,y_2 \leq 500$， 因此只要 $ C $ 超过500，则 $H(x_1, y_1,x_2, y_2) = H(x_1', y_1',x_2',y_2')$ 当且仅当 $x_1 = x_1', y_1 = y_1',x_2 = x_2', y_2 = y_2'$ 。（这里不证明，且不能太大，不要爆long long)。

若要判断 $(x_1, y_1, x_2, y_2)$ 是否存在，只需要考虑 $H(x_1, y_1, x_2, y_2)$ 是否在集合 $s$ 中即可。

s.count(x)：返回集合中x的数量（一般用于判断x是否存在）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll Hash(int a, int b, int c, int d) {
    return a + 514 * b + 514 * 514 * c + 514 * 514 * 514 * d;
}

set<ll> s;

ll ok(int a, int b, int c, int d) {
    return s.count(Hash(a, b, c, d));
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    ll ans1 = 0, ans2 = 0;
    for (int i = 1; i <= 2 * q; i++) {
        int num = 0;
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        ll H = Hash(x1, y1, x2, y2);
        if (s.count(H)) continue ;
        s.insert(H);
        if (x1 != x2) {
            if (ok(x1, y1 - 1, x1, y1) && ok(x2, y1 - 1, x2, y1) && ok(x1, y1 - 1, x2, y1 - 1)) num++;
            if (ok(x1, y1, x1, y1 + 1) && ok(x2, y1, x2, y1 + 1) && ok(x1, y1 + 1, x2, y1 + 1)) num++;
        }
        if (y1 != y2) {
            if (ok(x1 - 1, y1, x1 - 1, y2) && ok(x1 - 1, y1, x1, y1) && ok(x1 - 1, y2, x1, y2)) num++;
            if (ok(x1 + 1, y1, x1 + 1, y2) && ok(x1, y1, x1 + 1, y1) && ok(x2, y2, x2 + 1, y2)) num++;
        }
        if (i & 1) ans1 += num;
        else ans2 += num;
    }
    cout << ans1 << " " << ans2 << endl;


}

int main(){
    int T = 1;
//    cin >> T;
    while (T--) solve();
    return 0;
}