二维树状数组
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define ll long long
#define re(i,n) for(int i=0;i<n;i++)
;
int c[maxn][maxn];
int n, q;
int lowbit(int x){
return x&(-x);
}
void update(int x, int y){
; i-=lowbit(i))
; j -= lowbit(j))
c[i][j] ^= ;
}
int query(int x, int y){
;
for (int i = x; i <= n; i+=lowbit(i))
for (int j = y; j <= n; j += lowbit(j)){
ans ^= c[i][j];
}
return ans;
}
int main(){
//freopen("in.txt", "r", stdin);
int T; cin >> T;
while (T--){
scanf("%d%d", &n, &q);
memset(c, , sizeof(c));
while (q--){
]; scanf("%s", op);
] == 'Q'){
int x, y; scanf("%d%d", &x, &y);
printf("%d\n", query(x, y));
}
else{
int fx, fy, tx, ty; scanf("%d%d%d%d", &fx, &fy, &tx, &ty);
if (fx > tx)swap(fx, tx); if (fy > ty)swap(fy, ty);
fx--, fy--;
update(fx, fy);
update(tx, ty);
update(fx, ty);
update(tx, fy);
}
}
puts("");
}
;
}
二维线段树
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define ll long long
#define re(i,n) for(int i=0;i<n;i++)
#define ls(x) x<<1,f,mid
#define rs(x) x<<1|1,mid+1,t
;
int n, q;
int fx, fy, tx, ty, x, y;
int ans;
][maxn << ];
void updatey(int i, int j, int f, int t){
if (fy <= f&&ty >= t){
a[i][j] ^= ;
return;
}
;
if (fy <= mid)updatey(i,ls(j));
if (ty > mid)updatey(i, rs(j));
}
void updatex(int i, int f, int t){
if (fx<=f&&tx>=t){
updatey(i, , , n);
return;
}
;
if (fx <= mid)updatex(ls(i));
if (tx > mid)updatex(rs(i));
}
void queryy(int i, int j, int f, int t){
ans += a[i][j];
if (f == t)return;
;
if (y > mid)queryy(i,rs(j));
else queryy(i, ls(j));
}
void queryx(int i, int f, int t){
queryy(i, , , n);
if (f == t)return;
;
if (x > mid)queryx(rs(i));
else queryx(ls(i));
}
int main(){
//freopen("in.txt", "r", stdin);
int T; cin >> T;
while (T--){
scanf("%d%d", &n, &q);
memset(a, , sizeof(a));
/*应该用memset,用for循环一定要注意初始化的不是n,而是全部.
公元2015年9.20日在于此坑.
re(i, n + 1)re(j, n + 1)a[i][j] = 0;
*/
while (q--){
]; scanf("%s", op);
] == 'Q'){
scanf("%d%d",&x,&y);
ans = ;
queryx(, , n);
printf();
}
else{
scanf("%d%d%d%d", &fx, &fy, &tx, &ty);
if (fx > tx)swap(fx, tx); if (fy > ty)swap(fy, ty);
updatex(,,n);
//debug();
}
}
if (T)puts("");
}
;
}
zkw二维线段树 开区间写法
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
][maxn << ];
int n, q,sz;
bool yquery(int x, int y){
y += sz;
;
/*
因为1是哨兵节点,1必然始终都为0,不曾变化,所以算上1也无妨
*/
while (y){
ans ^= tr[x][y];
y >>= ;
}
return ans;
}
bool query(int x,int y){
x += sz;
;
while (x){
ans ^= yquery(x, y);
x >>= ;
}
return ans;
}
void yupdate(int x, int fy, int ty){
fy += sz - , ty += sz + ;
){
)tr[x][fy ^ ] ^= ;
)tr[x][ty ^ ] ^= ;
fy >>= , ty >>= ;
}
}
void update(int fx,int fy,int tx,int ty){
fx += sz - , tx += sz + ;
){
)yupdate(fx^, fy, ty);
)yupdate(tx ^ , fy, ty);
fx >>= , tx >>= ;
}
}
int main(){
//freopen("in.txt", "r", stdin);
int T; cin >> T;
while (T--){
scanf("%d%d", &n, &q);
sz = ; )sz <<= ;
memset(tr, , sizeof(tr));
while (q--){
]; scanf("%s", op);
] == 'Q'){
int x, y; scanf("%d%d", &x, &y);
bool ans = query(x, y);
printf("%d\n", ans);
}
else{
int fx, fy, tx, ty; scanf("%d%d%d%d", &fx, &fy, &tx, &ty);
if (fx > tx)swap(fx, tx); if (fy > ty)swap(fy, ty);
update(fx, fy, tx, ty);
}
}
puts("");
}
;
}
zwk二维线段树闭区间写法
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
][maxn << ];
int n, q,sz;
bool yquery(int x, int y){
y += sz-;
;
/*
因为1是哨兵节点,1必然始终都为0,不曾变化,所以算上1也无妨
*/
while (y){
ans ^= tr[x][y];
y >>= ;
}
return ans;
}
bool query(int x,int y){
x += sz-;
;
while (x){
ans ^= yquery(x, y);
x >>= ;
}
return ans;
}
/*
开区间=闭区间-两个端点.
所以,先处理两个端点之后就变成了开区间.
两个端点处理时要加上一个判断,l==r,如果相等,那就不能对同一个点处理两次,只处理一个点然后返回就行了;如果不等,那就先处理两端,再按照开区间的方式进行处理.
*/
void yupdate(int x, int fy, int ty){
fy += sz - , ty += sz -;
; return; }
tr[x][fy] ^= , tr[x][ty] ^= ;
){
)tr[x][fy ^ ] ^= ;
)tr[x][ty ^ ] ^= ;
fy >>= , ty >>= ;
}
}
void update(int fx,int fy,int tx,int ty){
fx += sz - , tx += sz - ;
if (fx == tx){
yupdate(fx, fy, ty); return;
}
yupdate(fx, fy, ty), yupdate(tx, fy, ty);
){
)yupdate(fx^, fy, ty);
)yupdate(tx ^ , fy, ty);
fx >>= , tx >>= ;
}
}
int main(){
freopen("in.txt", "r", stdin);
int T; cin >> T;
while (T--){
scanf("%d%d", &n, &q);
sz = ; ;
memset(tr, , sizeof(tr));
while (q--){
]; scanf("%s", op);
] == 'Q'){
int x, y; scanf("%d%d", &x, &y);
bool ans = query(x, y);
printf("%d\n", ans);
}
else{
int fx, fy, tx, ty; scanf("%d%d%d%d", &fx, &fy, &tx, &ty);
if (fx > tx)swap(fx, tx); if (fy > ty)swap(fy, ty);
update(fx, fy, tx, ty);
}
}
putchar();//换行是10,回车13,空格32
}
;
}