POJ - 2155 매트릭스 (2 차원 선분 트 리)

나 를 찍 어 문 제 를 보다.
제목: 초기 값 이 0 인 N×N 의 행렬, 지금 우 리 는 행렬 에 대해 두 가지 조작 을 할 수 있 습 니 다. C x1 y2 x2 y2 (x1, y1) 는 왼쪽 상단 에 있 고 (x2, y2) 는 오른쪽 하단 에 있 습 니 다. (x1, y1) 과 (x2, y2) 사이 의 행렬 대응 치 를 원래 와 반대 되 는 것 으로 바 꾸 고 Q x y 는 조회 (x, y) 의 값 으로 바 꿀 수 있 습 니 다.
분석: 눈대중 은 2 차원 선분 나무의 기초 문제 로 2 차원 선분 나무 와 1 차원 선분 나무의 관 계 는 2 차원 배열 과 1 차원 배열 의 관계 처럼 느껴 진다. 그러면 이 문제 에 대해 우 리 는 먼저 선분 나무 로 모든 줄 을 저장 한 다음 에 모든 잎 결점 에 모든 줄 의 구체 적 인 가 치 를 저장 할 수 있다. 사실은 조작 은 1 차원 과 유사 하 다.
참조 코드:

/*        */
#include
#include
#include
#include
#include

using namespace std;
#define lsonx rtx<<1
#define rsonx rtx<<1|1
#define lsony rty<<1
#define rsony rty<<1|1
const int maxn = 1e3+10;
int n,q;
struct SegTreeY{
        int l,r;
        int val;
};
struct SegTreeX{
        int l,r;
        SegTreeY sty[maxn<<2];
};
SegTreeX stx[maxn<<2];
int ans;

void Buildy( int l, int r, int rty, int rtx)
{
    stx[rtx].sty[rty].l = l;
    stx[rtx].sty[rty].r = r;
    stx[rtx].sty[rty].val = 0;
    if( l == r)
        return;
    int mid = (l+r)>>1;
    Buildy(l,mid,lsony,rtx);
    Buildy(mid+1,r,rsony,rtx);
}

void Buildx( int l, int r, int rtx)
{
    stx[rtx].l = l;
    stx[rtx].r = r;
    Buildy(1,n,1,rtx);
    if( l == r)
        return;
    int mid = (l+r)>>1;
    Buildx(l,mid,lsonx);
    Buildx(mid+1,r,rsonx);
}

void Updatey( int y1, int y2, int rty, int rtx)
{
    if( y1 == stx[rtx].sty[rty].l && y2 == stx[rtx].sty[rty].r)
    {
        stx[rtx].sty[rty].val = !stx[rtx].sty[rty].val;
        return;
    }
    int mid = (stx[rtx].sty[rty].l+stx[rtx].sty[rty].r)>>1;
    if( y2 <= mid)
        Updatey(y1,y2,lsony,rtx);
    else if( y1 > mid)
        Updatey(y1,y2,rsony,rtx);
    else
    {
        Updatey(y1,mid,lsony,rtx);
        Updatey(mid+1,y2,rsony,rtx);
    }
}

void Updatex( int x1, int y1, int x2, int y2, int rtx)
{
    if( x1 == stx[rtx].l && x2 == stx[rtx].r)
    {
        Updatey(y1,y2,1,rtx);
        return;
    }

    int mid = (stx[rtx].l+stx[rtx].r)>>1;
    if( x2 <= mid)
        Updatex(x1,y1,x2,y2,lsonx);
    else if( x1 > mid)
        Updatex(x1,y1,x2,y2,rsonx);
    else
    {
        Updatex(x1,y1,mid,y2,lsonx);
        Updatex(mid+1,y1,x2,y2,rsonx);
    }
}

void Queryy( int y, int rty, int rtx)
{
    ans ^= stx[rtx].sty[rty].val;
    if( stx[rtx].sty[rty].l == stx[rtx].sty[rty].r)
        return;
    int mid = (stx[rtx].sty[rty].l+stx[rtx].sty[rty].r)>>1;
    if( y <= mid)
        Queryy(y,lsony,rtx);
    else
        Queryy(y,rsony,rtx);
}

void Queryx( int x, int y, int rtx)
{
    Queryy(y,1,rtx);
    if( stx[rtx].l == stx[rtx].r)
        return;
    int mid = (stx[rtx].l+stx[rtx].r)>>1;
    if( x <= mid)
        Queryx(x,y,lsonx);
    else
        Queryx(x,y,rsonx);
}

int main()
{
    int T;
    scanf("%d",&T);
    while( T--)
    {
        scanf("%d%d",&n,&q);
        Buildx(1,n,1);
        char op[5];
        int x,y;
        int x1,y1,x2,y2;
        while( q--)
        {
            scanf("%s",op);
            if( op[0] == 'C')
            {
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                Updatex(x1,y1,x2,y2,1);
            }
            else if( op[0] == 'Q')
            {
                scanf("%d%d",&x,&y);
                ans = 0;
                Queryx(x,y,1);
                printf("%d
",ans);
            }
        }
        if( T)
            puts("");
    }

    return 0;
}