POJ 155 2 D線分ツリー

問題:n*nの01行列をあげて、それから2種類の操作(m回)C x 1 y 1 x 2 y 2がこの小さい矩形の内のすべての数字を1回異ならせて、Q x yは現在のこの点の値を尋ねるのはいくらですか?n<=1000 m<=50000. 考え方:少し卵が痛くて、昨日自分で5时间近く使って2つの2次元の線分の木のアルゴリズムを研究して、すべて失败して、実は私が考えた2番目のアルゴリズムとネット上のあの差は多くありません(后でネット上の考え方を见てやっと発见しました)、しかし私は段の更新のPushDownの问题を考えて、実はこの问题は段の更新で、これにより問題を簡略化することができ、線分樹である線分樹と考えやすいのが、線分樹がXを走って区間を確定してから線分樹がyを更新することであるが、いくつか注意すべき点である.Pushupを使わなくてもいいです.Pushdown(ポイントクエリなので、最初からセグメントクエリを考えていました.いろいろ自分で考えて、研究して、上下左右に更新しました.セグメントを平面にマッピングして、最後に悲劇になりました.あなたは知っています.)2.*大きな矩形を更新すると、彼の中の小さな矩形も更新に相当します.
(1,1)(5,5)(1,5),(5,1)この矩形のときは位置を見つけてそのままreturnしていましたが、実は(1,1)(2,2),(2,1)も更新していましたが、私たちは下り続けていませんので、答えを探すときは一緒に加算しなければなりません.これがポイントです.そう言えば分からないかもしれませんが、コードを何度も見ることができます.私はその时コードを见てすぐに分かりました.私が昨日考えたのは正解よりずっと难しいかもしれません.头が痛くて、考えが近いので、见ると分かります.しかし、谁でも、考えさえすれば、分かりやすいはずです.残念ながら、次のコードの考えは私が考えたものではありません.

#include
#include

#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
");
                else printf("0
");
            }
        }
        if(t) printf("
");
    }
    return 0;
}