题解 CF869E 【The Untended Antiquity】

Aleph1022 · 2018-08-20 23:11:43 · 题解

由于没有公共点这一性质，我们可以想到用二维树状数组来解决此题。

此题涉及二维树状数组的区间修改单点查询。

如果为增加障碍操作，就可以给这个障碍一个 ID，然后让这个区域内所有数字加上这个 ID。
很容易想到使用差分。

如果为拆除障碍操作，就把这个区域内所有数字减去这个 ID。

如果为查询操作，就查询这两个点的值是否相同。
不需要在意 ID 叠加，因为这样也是在同一个障碍之内。

于是有了第一版代码：

#include <cstdio>
#include <map>
#define lowbit(x) ((x) & -(x))
using namespace std;
int n,m,q,tot;
struct matrix
{
    int x1,y1,x2,y2;
    inline bool operator<(const matrix &a) const
    {
        if(x1 < a.x1)
            return 1;
        if(y1 < a.y1)
            return 1;
        if(x2 < a.x2)
            return 1;
        if(y2 < a.y2)
            return 1;
        return 0;
    }
};
int c[2510][2510];
map<matrix,int> hs;
inline void update(int x,int y,int k)
{
    for(register int i = x;i <= n;i += lowbit(i))
        for(register int j = y;j <= m;j += lowbit(j))
            c[i][j] += k;
}
inline int query(int x,int y)
{
    int ret = 0;
    for(register int i = x;i;i -= lowbit(i))
        for(register int j = y;j;j -= lowbit(j))
            ret += c[i][j];
    return ret;
}
inline void init()
{
    scanf("%d%d%d",&n,&m,&q);
}
inline void work()
{
    int opt,x1,y1,x2,y2;
    while(q--)
    {
        scanf("%d%d%d%d%d",&opt,&x1,&y1,&x2,&y2);
        if(opt == 1)
        {
            hs[(matrix){x1,y1,x2,y2}] = ++tot;
            update(x1,y1,tot);
            update(x1,y2 + 1,-tot);
            update(x2 + 1,y1,-tot);
            update(x2 + 1,y2 + 1,tot);
        }
        else if(opt == 2)
        {
            int num = hs[(matrix){x1,y1,x2,y2}];
            update(x1,y1,-num);
            update(x1,y2 + 1,num);
            update(x2 + 1,y1,num);
            update(x2 + 1,y2 + 1,-num);
        }
        else
        {
            if(query(x1,y1) == query(x2,y2))
                puts("Yes");
            else
                puts("No");
        }
    }
}
int main()
{
    init();
    work();
    return 0;
}

但是这个代码会在第 8 个点 WA 掉。

仔细思考后发现原来是 ID 的问题，这种 ID 分配方式使得有可能出现 1+3=2+2 的尴尬问题。

然后可以想到替代方案