codeforces 869E(哈希&二維樹狀數組)

把每個子矩陣哈希一下，增加操作就是樹狀數組加，删除就是減，然後判斷連通時就是判斷兩個點的hash值是否相等。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int n,m,q;
long long tree[2505][2505];
typedef pair<int,int> P;
map<pair<P,P>,long long>mp;
int lowbit(int i)
{
    return i&(-i);
}
void add(int l,int r,long long v)
{
    for(int i=l;i<=n;i+=lowbit(i))
        for(int j=r;j<=m;j+=lowbit(j))
        tree[i][j] += v;
}
long long get(int l,int r)
{
    long long ans = 0;
    for(int i=l;i;i-=lowbit(i))
        for(int j=r;j;j-=lowbit(j))
        ans += tree[i][j];
    return ans;
}
long long mod = 10037;
int main()
{
    long long s = 1;
    int op,x1,x2,y1,y2;
    scanf("%d%d%d",&n,&m,&q);
    while(q--)
    {
        scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
        if(op==1)
        {
            s*=mod;
            mp[make_pair(make_pair(x1,y1),make_pair(x2,y2))] = s;
            add(x1,y1,s); add(x2+1,y2+1,s); add(x1,y2+1,-s); add(x2+1,y1,-s);
        }
        else if(op==2)
        {
            long long oo = mp[make_pair(make_pair(x1,y1),make_pair(x2,y2))];
            add(x1,y1,-oo); add(x2+1,y2+1,-oo);
            add(x1,y2+1,oo); add(x2+1,y1,oo);
        }
        else if(op==3)
        {
            long long t1 = get(x1,y1);
            long long t2 = get(x2,y2);
            if(t1==t2) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}