cf869 E. The Untended Antiquity（二维树状数组，随机数）

本文主要是介绍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;
}

这篇关于cf869 E. The Untended Antiquity（二维树状数组，随机数）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！