首页 > 代码库 > TreeSegment2155

TreeSegment2155

这题是比较经典的二维树状数组,题意是给你个矩阵里面开始全是0,然后给你两种指令:1:‘C x1,y1,x2,y2’就是将左上角为x1,y1,右下角为x2,y2,的这个矩阵内的数字全部翻转,01,10,

2:‘Q x1 y1‘,输出a[x1][y1]的值

 

二维线段树,对于X方向上每一段【0,0】【1,1】他们的内层Y方向都是需要考虑所有情况

 

#include <cstring>

#include <cstdlib>

#include <cstdio>

#define LSON p << 1

#define RSON p << 1 | 1

#define MID( x, y ) (x) + (y) >> 1

#define TWO( x, y ) (x) + (y) << 1

#define M( x, y ) memset( (x), (y), sizeof(x) )

using namespace std;

 

struct node

{

    int u, d, val;

}n[2605][2605];

 

struct Node

{

    int l, r;

    node *next;

}N[2605];

 

int M, Q, ans;

 

void y_build( node *r, int p, int u, int d )// y_build( n[p], 1, 1, M + 1 );

{

    r[p].u = u, r[p].d = d, r[p].val = 0;//第一次运行到这里,表示X外层方向[1M+1],它的内层还有Y方向的[1m+1]线段

    if( d - u > 1 )

    {

        int m = MID( d, u );

        y_build( r, LSON, u, m );

        y_build( r, RSON, m, d );

    }

}

 

void build( int p, int l, int r )// build( 1, 1, M + 1 );

{

    N[p].l = l, N[p].r = r, N[p].next = n[p];//N[]X方向外层节点,N[P].NEXT对应内层Y线段第一条线段,这里n也是二维的,因此n的第一维

    if( r - l > 1 )//参数应该与N[]的参数一致。叶节点的形式是[1,2][2,3][3,4],分别对应Y坐标为123的点

    {

        int m = MID( l, r );

        build( LSON, l, m );

        build( RSON, m, r );

    }

    y_build( n[p], 1, 1, M + 1 );//每一段X线段都要建立内层Y节点,并且是包含所有区域的Yn[][]是二维的,这里带入的参数的是一维的

}

 

void y_modify( node *r, int p, int u, int d )

    if( r[p].u == u && r[p].d == d )//修改时,如果找到满足条件的根节点,那么子节点就不用考虑,因此不用PUSHDONW

    {

        r[p].val ^= 1;//01,10

        return;

    }

    int m = MID( r[p].u , r[p].d );

    if( m >= d )

        y_modify( r, LSON, u, d );

    else if( m <= u )

        y_modify( r, RSON, u, d );

    else

    {

        y_modify( r, LSON, u, m );

        y_modify( r, RSON, m, d );

    }

}

 

void modify( int p, int l, int r, int u, int d )// modify( 1, x1, x2 + 1, y1, y2 + 1 );

{

    if( N[p].l == l && N[p].r == r )

/*先从外层X找满足条件的,如果找到满足条件的根节点,那么子节点就不用考虑

这里不用pushdonw的原因在于,根节点信息更改以后,子节点表示区间操作对于

下面查询仍然有用,因为查询是根据从根节点一直到子节点所有的操作来决定*/

    {

        y_modify( N[p].next, 1, u, d );//找的以后,在这个外层X节点找内层(N[p].next)的

        return;

    }

    int m = MID( N[p].l, N[p].r );

    if( m >= r )

        modify( LSON, l, r, u, d );

    else if( m <= l )

        modify( RSON, l, r, u, d );

    else

    {

        modify( LSON, l, m, u, d );

        modify( RSON, m, r, u, d );

    }

}

  

void y_cal( node *r, int p, int u, int d )

{

    if( r[p].u <= u && r[p].d >= d )

    {

        ans ^= r[p].val; //一个节点的属性由该所有包含节点区间的操作次数的奇偶性决定,比如[1,9]范围的2节点,它的//奇偶性由[1,9],[1,5],[1,3],[2,3]区间上操作次数决定。

        if( r[p].d - r[p].u == 1 )

            return;

    }

    int m = MID( r[p].u, r[p].d ); 

    if( m >= d )

        y_cal( r, LSON, u, d );

    else if( m <= u )

    { 

        y_cal( r, RSON, u, d );

    }

}

 

void cal( int p, int l, int r, int u, int d )// cal( 1, x1, x1 + 1, y1, y1 + 1 );

{

    if( N[p].l <= l && N[p].r >= r )

    {

        y_cal( N[p].next, 1, u, d );

        if( N[p].r  - N[p].l == 1 )

            return;

    }

    int m = MID( N[p].l, N[p].r );

    if( m >= r )

        cal( LSON, l, r, u, d );

    else if( m <= l )

        cal( RSON, l, r, u, d );

}

 

int main()

{

    int T;

    scanf( "%d", &T );

    for( int t = 1; t <= T; ++t )

    {

        char op[5];

        int x1, x2, y1, y2;

        scanf( "%d %d", &M, &Q );

        build( 1, 1, M + 1 );

        for( int i = 0; i < Q; ++i )

        {

            scanf( "%s", op );

            if( op[0] == ‘C‘ )

            {

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

                modify( 1, x1, x2 + 1, y1, y2 + 1 );

            }

            else

            {

                ans = 0;

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

                cal( 1, x1, x1 + 1, y1, y1 + 1 );

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

                 

            }

        }

        if( t < T ) 

            puts( "" );

    }

    return 0;

}

TreeSegment2155