POJ 2155 2维线段树 || 2维BIT

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <map>

#include <set>

#include <stack>

#define mp make_pair

#define pa pair<int,int>

#define pb push_back

#define fi first

#define se second

using namespace std;

inline void Get_Int(int &X)

{

    X=;  char ch=getchar(); int f=;

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {X=X*+ch-''; ch=getchar();} X*=f;

}

inline void Put_Int(int X)

{

    char ch[]; int top=;

    if (X==) ch[++top]='';

    while (X) ch[++top]=X%+'',X/=;

    while (top) putchar(ch[top--]); putchar('\n');

}

//=======================================

const int Maxn=;

int x1,x2,y1,y2,Ans;

bool Key[Maxn][Maxn];

int n,Q,Kase;

void Modify_Y(int ox,int oy,int l,int r,int p,int q)

{

    if (l==p && r==q)

    {

        Key[ox][oy]^=;

        return;

    }

    int mid=(l+r)>>;

    if (q<=mid) Modify_Y(ox,oy<<,l,mid,p,q);

    if (p>=mid+) Modify_Y(ox,oy<<|,mid+,r,p,q);

    if (p<=mid && q>=mid+) Modify_Y(ox,oy<<,l,mid,p,mid),Modify_Y(ox,oy<<|,mid+,r,mid+,q);

}

void Modify_X(int ox,int l,int r,int p,int q)

{

    if (l==p && r==q)

    {

        Modify_Y(ox,,,n,y1,y2);

        return;

    }

    int mid=(l+r)>>;

    if (q<=mid) Modify_X(ox<<,l,mid,p,q);

    if (p>=mid+) Modify_X(ox<<|,mid+,r,p,q);

    if (p<=mid && q>=mid+) Modify_X(ox<<,l,mid,p,mid),Modify_X(ox<<|,mid+,r,mid+,q);

}

void Query_Y(int ox,int oy,int l,int r)

{

    Ans^=Key[ox][oy];

    if (l==r) return;

    int mid=(l+r)>>;

    if (y1<=mid) Query_Y(ox,oy<<,l,mid);

    if (y1>=mid+) Query_Y(ox,oy<<|,mid+,r);

}

void Query_X(int ox,int l,int r)

{

    Query_Y(ox,,,n);

    if (l==r) return;

    int mid=(l+r)>>;

    if (x1<=mid) Query_X(ox<<,l,mid);

    if (x1>=mid+) Query_X(ox<<|,mid+,r);

}

int main()

{

    Get_Int(Kase);

    for (int kase=;kase<=Kase;kase++)

    {

        Get_Int(n),Get_Int(Q);

        memset(Key,false,sizeof(Key));

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

        {

            char ch=getchar(); while (ch!='C' && ch!='Q') ch=getchar();

            if (ch=='C')

            {

                Get_Int(x1),Get_Int(y1),Get_Int(x2),Get_Int(y2);

                Modify_X(,,n,x1,x2);

            }

            if (ch=='Q')

            {

                Get_Int(x1),Get_Int(y1);

                Ans=;

                Query_X(,,n);

                Put_Int(Ans);

            }

        }

        putchar('\n');

    }

    return ;

}

线段树

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int Maxn=;

 int n,Q,Kase,c[Maxn][Maxn],x1,x2,y1,y2;

 inline int lowbit(int x) {return x&(-x);}

 inline void Modify(int x,int y)

 {

     for (int i=x;i<=n;i+=lowbit(i))

         for (int j=y;j<=n;j+=lowbit(j)) c[i][j]^=;

 }

 inline int Query(int x,int y)

 {

     int ret=;

     for (int i=x;i;i-=lowbit(i))

         for (int j=y;j;j-=lowbit(j)) ret^=c[i][j];

     return ret;

 }

 int main()

 {

     // freopen("c.in","r",stdin);

     scanf("%d",&Kase);

     for (int kase=;kase<=Kase;kase++)

     {

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

         memset(c,,sizeof(c));

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

         {

             char ch=getchar(); while (ch!='C' && ch!='Q') ch=getchar();

             if (ch=='C')

             {

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

                 Modify(x1,y1),Modify(x1,y2+),Modify(x2+,y1),Modify(x2+,y2+);

             }

             if (ch=='Q')

             {

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

                 printf("%d\n",Query(x1,y1));

             }

         }

         puts("");

     }

     return ;

 }

BIT