首页 > 代码库 > TreeSegment2155
TreeSegment2155
这题是比较经典的二维树状数组，题意是给你个矩阵里面开始全是0，然后给你两种指令：1：‘C x1,y1,x2,y2’就是将左上角为x1,y1,右下角为x2,y2,的这个矩阵内的数字全部翻转，0变1,1变0,；
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外层方向[1，M+1]，它的内层还有Y方向的[1，m+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坐标为1，2，3的点
{
int m = MID( l, r );
build( LSON, l, m );
build( RSON, m, r );
}
y_build( n[p], 1, 1, M + 1 );//每一段X线段都要建立内层Y节点，并且是包含所有区域的Y。n[][]是二维的，这里带入的参数的是一维的
}
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;//0变1,1变0
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