Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquity

题目链接http://codeforces.com/contest/869/problem/E

解题心得：

1、1，x1，y1，x2，y2 以（x1,y1）为左上角（x2,y2）为右下角的矩形，四边建墙。

2，x1，y1，x2，y2 以（x1,y1）为左上角（x2,y2）为右下角的矩形，拆除墙（肯定存在）。

3，x1，y1，x2，y2问是否可以从（x1,y1）走到（x2,y2）（没墙阻隔）。

2、先要标记每个点的状态，将用墙围起来的部分赋予一个值，如果两个点的值相同说明在同一个墙内，或者都没有墙阻拦，但是怎么赋予一个值能够代表这个点的状态，这就要hash，让不同的围困情况有不同的状态值。

3、hash出状态值之后需要标记，遍历肯定会超时，这就需要使用树状数组，二维的树状数组，和一维用法一样。在使用树状数组的时候要注意一下边界的问题

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3000;

const int _hash = 233;

typedef long long ll;

ll maps[maxn][maxn];

ll n,m,q;

ll lowbit(ll x)

{

    return x&-x;

}

void updata(ll x,ll y,ll val)

{

    for(ll i=x; i<=n; i+=lowbit(i))

        for(ll j=y; j<=m; j+=lowbit(j))

            maps[i][j] += val;

}

void updata(ll x1,ll y1,ll x2,ll y2,ll val)

{

    //需要注意一下边界的问题

    updata(x1,y1,val);

    updata(x1,y2+1,-val);

    updata(x2+1,y1,-val);

    updata(x2+1,y2+1,val);

}

ll query(ll x,ll y)

{

    ll ans = 0;

    for(ll i=x;i;i-=lowbit(i))

        for(ll j=y;j;j-=lowbit(j))

            ans += maps[i][j];

    return ans;

}

void query(ll x1,ll y1,ll x2,ll y2)

{

    ll ans1,ans2;

    ans1 = ans2 = 0;

    ans1 = query(x1,y1);

    ans2 = query(x2,y2);

    if(ans1 == ans2)

        printf("Yes\n");

    else

        printf("No\n");

}

int main()

{

    scanf("%lld%lld%lld",&n,&m,&q);

    while(q--)

    {

        ll mark,x1,x2,y1,y2;

        scanf("%lld%lld%lld%lld%lld",&mark,&x1,&y1,&x2,&y2);

        ll temp = 1;

        //hash

        temp = temp*_hash + x1;

        temp = temp*_hash + x2;

        temp = temp*_hash + y1;

        temp = temp*_hash + y2;

        if(mark == 2)//拆除状态是建立状态的倒数

            temp = -temp;

        else if(mark == 3)

        {

            query(x1,y1,x2,y2);

            continue;

        }

        updata(x1,y1,x2,y2,temp);

    }

}

巴特西

Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquity

最新文章

热门文章