POJ2155二维线段树

题意：

给一个n*n的01矩阵，然后有两种操作（m次）C x1 y1 x2 y2是把这个小矩形内所有数字异或一遍，Q x y 是询问当前这个点的值是多少？n<=1000 m<=50000.

思路：

做的有点蛋疼，昨天自己用了将近5个小时自己研究了两个二维线段树的算法，都失败了，其实我想到的第二个算法和网上那个差不多（后来看网上的思路才发现），但是我考虑的是段更新的PushDown的问题，其实这个题目是段更新，*点询问*，根据这个可以简化问题，思路很容易想到可以是线段树的线段树，就是线段树跑X确定区间后再线段树去更新y,但是有几点需要注意

1. 可以不用Pushup，Pushdown(因为是点询问，一开始我就考虑段询问，各种自己设想，研究而且还写了个上下左右更新，就是把线段映射成平面，最后悲剧了..你懂的)

2.*当更新大矩形的时候那么他里面的小矩形也相当于更新了，就是假如现在更新

（1,1）（5,5）（1,5），（5,1）这个矩形的时候我们是找到位置直接就return了，其实（1,1）（2,2），（1,2），（2,1）也更新了，但是我们没有继续往下走，所以当我们寻找答案的时候要一路加过来，这个是重点，这么说可能不懂，但是可以看几遍代码，我当时看了下代码马上就懂了，可能是我昨天想的要比正解难很多，想到头疼，而且思路相近，所以一看就懂了，但是不管是谁，只要考虑过，应该很容易懂，很可惜下面的代码的思路并不是我自己想出来的。

#include<stdio.h>

#include<string.h>

#define xlson xl ,xmid ,xt << 1

#define xrson xmid+1 ,xr ,xt << 1 | 1

#define ylson yl ,ymid ,yt << 1

#define yrson ymid+1 ,yr ,yt << 1 | 1

#define N 1005

int cnt[N<<2][N<<2] ,n ,ans;

void UpdateY(int yl ,int yr ,int yt ,int c ,int d ,int xt)

{

    if(c <= yl && d >= yr)

    {

        cnt[xt][yt] ++;

        return ;

    }

    int ymid = (yl + yr) >> 1;

    if(c <= ymid) UpdateY(ylson ,c ,d ,xt);

    if(d > ymid) UpdateY(yrson ,c ,d ,xt);

    return ;

}

void UpdateX(int xl ,int xr ,int xt ,int a ,int b ,int c ,int d)

{

    if(a <= xl && b >= xr)

    {

        UpdateY(1 ,n ,1 ,c ,d ,xt);

        return ;

    }

    int xmid = (xl + xr) >> 1;

    if(a <= xmid) UpdateX(xlson ,a ,b ,c ,d);

    if(b > xmid) UpdateX(xrson ,a ,b ,c ,d);

    return ;

}

void QueryY(int yl ,int yr ,int yt ,int b ,int xt)

{

    ans += cnt[xt][yt];

    if(yl == yr) return ;

    int ymid = (yl + yr) >> 1;

    if(b <= ymid) QueryY(ylson ,b ,xt);

    else QueryY(yrson ,b ,xt);

    return ;

}

void QueryX(int xl ,int xr ,int xt ,int a ,int b)

{

    QueryY(1 ,n ,1 ,b ,xt);

    if(xl == xr) return ;

    int xmid = (xl + xr) >> 1;

    if(a <= xmid) QueryX(xlson ,a ,b);

    else QueryX(xrson ,a ,b);

    return ;

}

int main ()

{

    int t ,m ,i ,x1 ,y1 ,x2 ,y2;

    char str[5];

    scanf("%d" ,&t);

    while(t--)

    {

        scanf("%d %d" ,&n ,&m);

        memset(cnt ,0 ,sizeof(cnt));

        while(m--)

        {

            scanf("%s" ,str);

            if(str[0] == 'C')

            {

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

                UpdateX(1 ,n ,1 ,x1 ,x2 ,y1 ,y2);

            }

            else

            {

                scanf("%d %d" ,&x1 ,&y1);

                ans = 0;

                QueryX(1 ,n ,1 ,x1 ,y1);

                if(ans % 2)

                printf("1\n");

                else printf("0\n");

            }

        }

        if(t) printf("\n");

    }

    return 0;

}

巴特西

POJ2155二维线段树

最新文章

热门文章