CF869E The Untended Antiquity 题解

namespace lowspeed_song {

inline void init() {
}

mt19937_64 mt(time(0));
uniform_int_distribution<u64> dist(0, ULLONG_MAX);

struct BIT {
    u64 tree[2510][2510];
    inline BIT() { memset(tree, 0, sizeof tree); }
    inline void add(int x, int y, u64 v) {
        for (int i = x; i < 2510; i += (i &- i))
            for (int j = y; j < 2510; j += (j &- j))
                tree[i][j] += v;
    }
    inline u64 qry(int x, int y) {
        u64 sum = 0;
        for (int i = x; i; i -= (i &- i))
            for (int j = y; j; j -= (j &- j))
                sum += tree[i][j];
        return sum;
    }
} fwt;

inline void sol() {
    int n, m, q; cin >> n >> m >> q;
    map<tuple<int, int, int, int>, u64> mp;
    while (q--) {
        int o; cin >> o;
        if (o == 1) {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            u64 val = dist(mt);
            mp[{x1, y1, x2, y2}] = val;
            fwt.add(x2 + 1, y2 + 1, val), fwt.add(x1, y1, val);
            fwt.add(x1, y2 + 1, -val), fwt.add(x2 + 1, y1, -val);
        } else if (o == 2) {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            u64 val = -mp[{x1, y1, x2, y2}];
            fwt.add(x2 + 1, y2 + 1, val), fwt.add(x1, y1, val);
            fwt.add(x1, y2 + 1, -val), fwt.add(x2 + 1, y1, -val);
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << ((fwt.qry(x1, y1) == fwt.qry(x2, y2)) ? "Yes" : "No") << '\n';
        }
    }
}

} // namespace lowspeed_song