題目連結
題意:
兩種操作:
\(1. C\) \(x_1\) \(y_1\) \(x_2\) \(y_2\),将右上點為\((x_1, y_1)\),左下點為\((x_2, y_2)\)内的值全都異或1。
\(2. Q\) \(x\) \(y\),查詢點(\(x\), \(y\))的值。
思路:
\(1.\)二維線段樹區間更新+單點查詢。
與一維線段樹區間更新不同,二維區間更新時懶惰lazy标記不需要下放,查詢時需将包含該點的區間的懶惰标記全都記錄。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
// #include <unordered_map>
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long
const double eps = 1e-15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
using namespace std;
#define lson rt << 1
#define rson rt << 1 | 1
int t[maxn << 2][maxn << 2], n;
void rebuild(int rt, int l, int r, int num){
t[num][rt] = 0;
if(l == r)return ;
int mid = l + r >> 1;
rebuild(lson, l, mid, num), rebuild(rson, mid + 1, r, num);
}
void build(int rt, int l, int r){
rebuild(1, 1, n, rt);
if(l == r)return;
int mid = l + r >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
}
void reupdate(int rt, int l, int r, int Y1, int Y2, int num){
if(Y1 <= l && r <= Y2)return void(t[num][rt] ^= 1);
int mid = l + r >> 1;
if(Y1 <= mid)reupdate(lson, l, mid, Y1, Y2, num);
if(mid < Y2)reupdate(rson, mid + 1, r, Y1, Y2, num);
}
void update(int rt, int l, int r, int X1, int Y1, int X2, int Y2){
if(X1 <= l && r <= X2)return void(reupdate(1, 1, n, Y1, Y2, rt));
int mid = l + r >> 1;
if(X1 <= mid)update(lson, l, mid, X1, Y1, X2, Y2);
if(mid < X2)update(rson, mid + 1, r, X1, Y1, X2 ,Y2);
}
int requery(int rt, int l, int r, int Y1, int num){
int ret = 0;
ret ^= t[num][rt];
if(l == r)return ret;
int mid = l + r >> 1;
if(Y1 <= mid)return ret ^ requery(lson, l, mid, Y1, num);
else return ret ^ requery(rson, mid + 1, r, Y1, num);
}
int query(int rt, int l, int r, int X1, int Y1){
int ret = 0;
ret ^= requery(1, 1, n, Y1, rt);
if(l == r)return ret;
int mid = l + r >> 1;
if(X1 <= mid)return ret ^ query(lson, l, mid, X1, Y1);
else return ret ^ query(rson, mid + 1, r, X1, Y1);
}
int main(){
int t, q, a1, b1, a2, b2;
scanf("%d", &t);
while(t --){
scanf("%d%d", &n, &q);
build(1, 1, n);
char s[2];
while(q --){
scanf("%s", s);
if(s[0] == 'C'){
scanf("%d%d%d%d", &a1, &b1, &a2, &b2);
update(1, 1, n, a1, b1, a2, b2);
}
else{
scanf("%d%d", &a1, &b1);
int ans = query(1, 1, n, a1, b1);
printf("%d\n", ans);
}
}
puts("");
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
// #include <unordered_map>
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long
const double eps = 1e-15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int maxn = 1e3 + 10;
using namespace std;
#define lson rt << 1
#define rson rt << 1 | 1
int t[maxn][maxn], n;
void update(int x, int y){
while(x <= n){
int dy = y;
while(dy <= n)t[x][dy] += 1, dy += lowbit(dy);
x += lowbit(x);
}
}
int getsum(int x, int y){
int ret = 0;
while(x){
int dy = y;
while(dy)ret += t[x][dy], dy -= lowbit(dy);
x -= lowbit(x);
}
return ret;
}
int main(){
int t1, q, a1, b1, a2, b2;
scanf("%d", &t1);
while(t1 --){
memset(t, 0, sizeof t);
scanf("%d%d", &n, &q);
char s[2];
while(q --){
scanf("%s", s);
if(s[0] == 'C'){
scanf("%d%d%d%d", &a1, &b1, &a2, &b2);
update(a1, b1), update(a2 + 1, b1), update(a1, b2 + 1), update(a2 + 1, b2 + 1);
}
else{
scanf("%d%d", &a1, &b1);
int ans = getsum(a1, b1) % 2;
printf("%d\n", ans);
}
}
puts("");
}
return 0;
}