首先人人都能想到是线段树，不过二维线段树肯定会MLE+TLE的。
我们换一种想法，不去修改整个区间，而是修改一个点：开横竖两个线段树，分别记录哪些行和列被修改了。因为如果两阵红雾碰撞，则会因为密度过大而沉降消失，所以自然想到亦或。
统计的时候求出这个矩形内有哪些行和列被修改了，接着把这些行和列的长度累加到答案中，但这样的话交点处不仅会重加，而实际上应该是0，所以在减去两倍的被修改的行，列数。
综上：单点亦或修改，区间查询。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m, q; 38 struct Tree 39 { 40 int l[maxn << 2], r[maxn << 2], sum[maxn << 2]; 41 Tree() 42 { 43 Mem(l, 0); Mem(r, 0); 44 Mem(sum, 0); 45 } 46 void build(int L, int R, int now) 47 { 48 l[now] = L; r[now] = R; 49 if(L == R) return; 50 int mid = (L + R) >> 1; 51 build(L, mid, now << 1); 52 build(mid + 1, R, now << 1 | 1); 53 } 54 void update(int idx, int now) 55 { 56 if(l[now] == r[now]) {sum[now] ^= 1; return;} 57 int mid = (l[now] + r[now]) >> 1; 58 if(idx <= mid) update(idx, now << 1); 59 else update(idx, now << 1 | 1); 60 sum[now] = sum[now << 1] + sum[now << 1 | 1]; 61 } 62 int query(int L, int R, int now) 63 { 64 if(L == l[now] && R == r[now]) return sum[now]; 65 int mid = (l[now] + r[now]) >> 1; 66 if(R <= mid) return query(L, R, now << 1); 67 else if(L > mid) return query(L, R, now << 1 | 1); 68 else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1); 69 } 70 }X, Y; 71 72 int main() 73 { 74 n = read(); m = read(); q = read(); 75 X.build(1, n, 1); Y.build(1, m, 1); 76 for(int i = 1; i <= q; ++i) 77 { 78 int d = read(); 79 if(d == 1) 80 { 81 int x = read(), y = read(); 82 X.update(x, 1); Y.update(y, 1); 83 } 84 else 85 { 86 int xa = read(), ya = read(), xb = read(), yb = read(); 87 int a = X.query(xa, xb, 1), b = Y.query(ya, yb, 1); 88 write((ll)a * (ll)(yb - ya + 1) + (ll)b * (ll)(xb - xa + 1) - (ll)a * b * 2); 89 enter; 90 } 91 } 92 return 0; 93 }