該題就是簡單的二維樹狀數(shù)組，保留一份棋盤的最新狀態(tài)即可，樹狀數(shù)組里面就只保留在原有基礎(chǔ)上增加或者減少的某一種餃子的數(shù)量。

代碼如下：

#include <cstring> #include <cstdlib> #include <cstdio> using namespace std;char op[5];char G[1050][1050];int cc[1050][1050]; // 數(shù)組中存儲韭菜餃的數(shù)量，白菜餃的數(shù)量通過總數(shù)量減去韭菜餃來求void init() {int k = 0; // 定義韭菜為1，白菜為0for (int i = 1; i <= 1024; ++i) {for (int j = 1; j <= 1025; ++j) { // 由于一行的結(jié)束和另一行的開始種類相同，所以多加了一列來翻轉(zhuǎn)kG[i][j] = (k ^= 1);}} }int lowbit(int x) {return x & -x; }void modify(int x, int y, int val) {for (int i = x; i <= 1024; i += lowbit(i)) {for (int j = y; j <= 1024; j += lowbit(j)) {cc[i][j] += val;}} }int sum(int x, int y) {int tot = 0;for (int i = x; i > 0; i -= lowbit(i)) {for (int j = y; j > 0; j -= lowbit(j)) { tot += cc[i][j];}}return tot; }int main() {int T, a, b, c, d, k;int A, B, C, S;while (scanf("%d", &T) == 1) {init();memset(cc, 0, sizeof (cc));while (T--) { scanf("%s", op);if (op[0] == 'R') {scanf("%d %d %d %d", &a, &b, &c, &d);A = sum(c, d) - sum(c, b-1) - sum(a-1, d) + sum(a-1, b-1);if ((a + b) & 1) { // 白菜多數(shù)S = (c-a+1)*(d-b+1) / 2;}else {S = ((c-a+1)*(d-b+1) + 1)/ 2;}B = S + A;C = (c-a+1)*(d-b+1) - B;printf("%d %d\n", B, C);}else { // 'A' 為韭菜，‘B’ 為白菜scanf("%d %d", &a, &b);k = op[0] == 'A'; // 1為韭菜，0為白菜if (k != G[a][b]) {G[a][b] = k;if (k) {modify(a, b, 1);}else {modify(a, b, -1);}}}}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Lyush/archive/2012/08/01/2617694.html

總結(jié)

以上是生活随笔為你收集整理的HDU-水饺基情 二维树状数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。