解题思路

很巧妙的一道题。我们可以考虑用二维树状数组去做，新建障碍视为在二位数组中对一个矩形区域增加一个值，而移除障碍就是减掉这个值，查询就是判断两个点的值是否一致。

那么问题来了，这个值要加多少呢？这个题给了很巧妙的做法，就是每次随机一个数（可以去 Editorial 看一下证明）。当然其他不会导致重复的生成方式也是可以的。

参考代码

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

const long long p = 3;
const int MAX = 2500;

int n, m, q, t, x1, y1, x2, y2;
long long c[MAX+2][MAX+2];
map<pair<pair<int, int>, pair<int, int> >, long long> mp;

int LowBit(int x) {
    return x&(-x);
}

void Add(int x, int y, long long v) {
    for(int i=x; i<=n; i+=LowBit(i)) {
        for(int j=y; j<=m; j+=LowBit(j)) {
            c[i][j] += v;
        }
    }
}

long long Sum(int x, int y) {
    long long sum = 0;
    for(int i=x; i>=1; i-=LowBit(i)) {
        for(int j=y; j>=1; j-=LowBit(j)) {
            sum += c[i][j];
        }
    }

    return sum;
}

int main(int argc, char const *argv[]) {
    scanf("%d %d %d", &n, &m, &q);
    long long val = 1;
    while(q--) {
        scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);
        if(t == 1) {
            val *= p;
            mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))] = val;
            Add(x1, y1, val);
            Add(x1, y2+1, -val);
            Add(x2+1, y1, -val);
            Add(x2+1, y2+1, val);
        }
        if(t == 2) {
            long long tmp = mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))];
            Add(x1, y1, -tmp);
            Add(x1, y2+1, tmp);
            Add(x2+1, y1, tmp);
            Add(x2+1, y2+1, -tmp);
        }
        if(t == 3) {
            if(Sum(x1, y1) == Sum(x2, y2))
                printf("Yes\n");
            else printf("No\n");
        }
    }
    
    return 0;
}