POJ 2155 二维线段树
思路：二维线段树就是每个节点套一棵线段树的树。
刚开始因为题目是求A[I,J]，然后在y查询那直接ans^=Map[i][j]的时候没看懂，后面自己把图画出来了才理解。
因为只有0和1，所以可以用异或来搞，而不需要每次都需要修改。
#include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 510010 #define maxn 4010 using namespace std; typedef long long ll; typedef unsigned long long ull; bool Map[maxn][maxn]; int n,q,t,ans; void update_y(int i,int j,int l,int r,int y1,int y2) { if(l==y1&&r==y2) {Map[i][j]^=1;return ;} int mid=(l+r)>>1; if(y2<=mid) update_y(i,llson,y1,y2); else if(y1>mid) update_y(i,rrson,y1,y2); else { update_y(i,llson,y1,mid); update_y(i,rrson,mid+1,y2); } } void update_x(int i,int l,int r,int x1,int x2,int y1,int y2) { if(l==x1&&r==x2) { update_y(i,1,1,n,y1,y2); return ; } int mid=(l+r)>>1; if(x2<=mid) update_x(lson,x1,x2,y1,y2); else if(x1>mid) update_x(rson,x1,x2,y1,y2); else { update_x(lson,x1,mid,y1,y2); update_x(rson,mid+1,x2,y1,y2); } } void query_y(int i,int j,int l,int r,int y) { ans^=Map[i][j]; if(l==r) return ; int mid=(l+r)>>1; if(y<=mid) query_y(i,llson,y); else query_y(i,rrson,y); } void query_x(int i,int l,int r,int x,int y) { query_y(i,1,1,n,y); if(l==r) return ; int mid=(l+r)>>1; if(x<=mid) query_x(lson,x,y); else query_x(rson,x,y); } int main() { //freopen("test.txt","r",stdin); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); mem(Map,0); while(q--) { char s[2]; scanf("%s",s); ans=0; if(s[0]=='C') { int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); update_x(1,1,n,x1,x2,y1,y2); } else { int x,y; scanf("%d%d",&x,&y); query_x(1,1,n,x,y); printf("%d\n",ans); } } if(t) puts(""); } return 0; }