二维线段树 poj-2155

题意:t组样例，输入 n,m,表示n*n的矩阵进行m次操作，C: 输入两个坐标，组成的矩形进行取反操作，Q:对输的坐标位置输入其值。

思路：一开始想的是用1000(表示x轴)个线段树（对每段y进行操作）来记录，也是二维的，第一维暴力，第二维线段树，结果TI ,原来还有二维线段树，每个对应的节点都有一颗线段树（好像跟我的差不多）

更新：先找到x对应的区间，对相应的y区间修改。

查询：对于每次找的x 都进行一次查询y

#include<string.h>

#include<stdio.h>

#include<algorithm>

#include<iostream>

using namespace std;

int e[4040][4040],n;

/*x对应的每个节点都有一颗线段树*/

void updatey(int x,int y,int l,int r,int o,int t)

{

    if(x<=l&&y>=r)

    {

        e[t][o]++;/*跟下面查询有关*/

        return;

    }

    int mid=(l+r)>>1;

    if(x<=mid) updatey(x,y,l,mid,o<<1,t);

    if(y>mid) updatey(x,y,mid+1,r,o<<1|1,t);

    return ;

}

void updatex(int x,int y,int t1,int t2,int l,int r,int o)

{

    if(x<=l&&y>=r)

    {

        updatey(t1,t2,1,n,1,o);

        return ;

    }

    int mid=(l+r)>>1;

    if(x<=mid) updatex(x,y,t1,t2,l,mid,o<<1);

    if(y>mid) updatex(x,y,t1,t2,mid+1,r,o<<1|1);

    return ;

}

int ans;

void queryy(int x,int l,int r,int o,int t)

{

    ans+=e[t][o];

    if(l==r)

        return ;

    int mid=(l+r)>>1;

    if(x<=mid) queryy(x,l,mid,o<<1,t);

    else queryy(x,mid+1,r,o<<1|1,t);

    return ;

}

void queryx(int x,int y,int l,int r,int o)/*查询所有的x线段树*/

{

    queryy(y,1,n,1,o);/*每个节点x都查询y线段树*/

    if(l==r)

        return ;

    int mid=(l+r)>>1;

    if(x<=mid) queryx(x,y,l,mid,o<<1);

    else queryx(x,y,mid+1,r,o<<1|1);

}

int main()

{

    int t,m;

    scanf("%d",&t);

    while(t--)

    {

        memset(e,0,sizeof(e));

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

        char s[10];

        int x1,y1,x2,y2;

        for(int i=1;i<=m;i++)

        {

            scanf("%s",s);

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

            {

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

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

            }

            else if(s[0]=='Q')

            {

                ans=0;

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

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

                printf("%d\n",ans%2);

            }

        }

        printf("\n");

    }

    return 0;

}

巴特西

二维线段树 poj-2155

最新文章

热门文章