cf869 E. The Untended Antiquity(二维树状数组,随机数)

https://codeforces.com/contest/869/problem/E

题意:

有 \(n×m\) 个网格,\(x,y\) 表示位于第 \(x\) 行第 \(y\) 列的那个方格。输入 \(x1,y1,x2,y2\),进行三种操作:

操作 1:以 \(x1,y1,x2,y2\) 为对角线的两端可以确定一个矩形(保证 \(x1\le x2,y1\le y2\)),沿着该矩形的外周长造一圈围栏。保证围栏不相交

操作 2:拆除该矩形决定的围栏(保证拆除前存在该围栏)

操作 3:\(x1,y1,x2,y2\) 决定两个点,询问从一个点能否走到另一点

思路:

只有当两个点分别属于的矩形集合完全相同时才能连通。用二维树状数组,在矩形的左上、右下端点加一随机数,在左下、右上端点减去该随机数。加也可换为异或等操作

随机数由 \(x1,y1,x2,y2\) 确定,保证了每个矩形留下的 “痕迹” 是唯一的。不用随机数的话也可用别的线性函数或者其他方法得到一个哈希值,不冲突就行

在矩形的两个端点加 \(d\) ,其他两个端点减 \(d\) 也很巧妙。反正最后两点的前缀和 \(sum\) 相同就代表所在的矩形集合完全相同

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;
using ll = long long;

int n, m, q, op, x1, y1, x2, y2, A, B, C, D;

ll tree[2510][2510];
int lowbit(int x) {return x&-x;}
void add(int x,int y,ll num)
{
    for(int i=x; i<=n; i+=lowbit(i))
        for(int j=y; j<=m; j+=lowbit(j))
            tree[i][j]+=num;
}
ll sum(int x,int y)
{
    ll res=0;
    for(int i=x; i>=1; i-=lowbit(i))
        for(int j=y; j>=1; j-=lowbit(j))
            res+=tree[i][j];
    return res;
}

void modify(int sgn)
{
    ll d = ((ll)A*x1+(ll)B*y1+(ll)C*x2+(ll)D*y2) * sgn;
    add(x1, y1, d); add(x2+1, y2+1, d);
    add(x1, y2+1, -d); add(x2+1, y1, -d);
}
void init()
{
    srand(time(0)); A = rand(); B = rand(); C = rand(); D = rand();
}
signed main()
{
    init(); cin >> n >> m >> q;
    while(q--)
    {
        scanf("%d%d%d%d%d", &op,&x1,&y1,&x2,&y2);
        if(op == 1) modify(1);
        else if(op == 2) modify(-1);
        else puts(sum(x1,y1) == sum(x2,y2) ? "Yes" : "No");
    }

    return 0;
}

上一篇:C#设计模式之二工厂方法模式(Factory Method Pattern)【创建型】


下一篇:彻底弄清楚前缀和与差分!