這題我知道是用樹狀數(shù)組，可是好久沒打樹狀數(shù)組了，就想用普通方法水過去~~結(jié)果……結(jié)果……水了好多方法都水不過，出題人真狠吶……我的水方法是對于每一次查詢，初始化ans=(x2-x1+1)*(y2-y1+1)，然后對于這個操作之前的每一個操作，對ans進行處理即可。可是交上去TLE，加上輸入外掛，還是TLE，又加一個優(yōu)化，即對于每一個查詢，如果查詢的區(qū)間小于10000，就直接數(shù)，還是TLE，服了，還是打樹狀數(shù)組吧~~~~~~~~~~~~~

我的水代碼：

/** hdu1892/win.cpp* Created on: 2012-11-1* Author : ben*/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; const int MAXN = 1010; typedef struct Ope{int x1, x2, y1, y2;int n;char type; }Ope; vector<Ope> ope; int room[MAXN][MAXN]; inline int get_int() {int res = 0, ch;while (!((ch = getchar()) >= '0' && ch <= '9')) {if (ch == EOF)return 1 << 30;}res = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9')res = res * 10 + (ch - '0');return res; } inline bool inrect(int &x, int &y, int &x1, int &y1, int &x2, int &y2) {return x >= x1 && x <= x2 && y >= y1 && y <= y2; } void work2(int x1, int y1, int x2, int y2, int n) {int ans = (x2 - x1 + 1) * (y2 - y1 + 1);for(int i = 0; i < n; i++) {if(ope[i].type == 'M') {if(inrect(ope[i].x1, ope[i].y1, x1, y1, x2, y2)) {ans -= ope[i].n;}if(inrect(ope[i].x2, ope[i].y2, x1, y1, x2, y2)) {ans += ope[i].n;}}else if(ope[i].type == 'A') {if(inrect(ope[i].x1, ope[i].y1, x1, y1, x2, y2)) {ans += ope[i].n;}}else if(ope[i].type == 'D') {if(inrect(ope[i].x1, ope[i].y1, x1, y1, x2, y2)) {ans -= ope[i].n;}}}printf("%d\n", ans); } void work1(Ope &o) {int ans = (o.x2 - o.x1 + 1) * (o.y2 - o.y1 + 1);if(ans < 1000) {ans = 0;for(int i = o.x1; i <= o.x2; i++) {for(int j = o.y1; j <= o.y2; j++) {ans += room[i][j];}}printf("%d\n", ans);o.type = 0;} } inline void input(Ope &o) {char c = getchar();int x1, y1, x2, y2;while(c <= ' ') {c = getchar();}o.type = c;if(c == 'S') {x1 = get_int(), y1 = get_int(), x2 = get_int(), y2 = get_int();o.x1 = min(x1, x2); o.x2 = max(x1, x2);o.y1 = min(y1, y2); o.y2 = max(y1, y2);work1(o);}else if(c == 'A') {o.x1 = get_int(), o.y1 = get_int(), o.n = get_int();room[o.x1][o.y1] += o.n;}else if(c == 'D') {o.x1 = get_int(), o.y1 = get_int(), o.n = get_int();if(room[o.x1][o.y1] < o.n) {o.n = room[o.x1][o.y1];}room[o.x1][o.y1] -= o.n;}else if(c == 'M') {o.x1 = get_int(), o.y1 = get_int(), o.x2 = get_int(), o.y2 = get_int();o.n = get_int();if(room[o.x1][o.y1] < o.n) {o.n = room[o.x1][o.y1];}room[o.x1][o.y1] -= o.n;room[o.x2][o.y2] += o.n;} }int main() { #ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin); #endifint T, Q;T = get_int();for(int t = 1; t <= T; t++) {printf("Case %d:\n", t);Q = get_int();fill(*room, *room + MAXN * MAXN, 1);ope.resize(Q);for_each(ope.begin(), ope.end(), input);for(int i = 0, len = (int)ope.size(); i < len; i++) {if(ope[i].type == 'S') {work2(ope[i].x1, ope[i].y1, ope[i].x2, ope[i].y2, i);}}}return 0; }

?

二維樹狀數(shù)組代碼：

/** hdu1892/win.cpp* Created on: 2011-9-6* Author : ben*/ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <map> using namespace std; typedef long long LL; const int MAXN = 1005; LL data[MAXN][MAXN]; int Row = 1001, Col = 1001; inline int Lowbit(const int &x) { // x > 0return x & (-x); } LL sum(int x, int y) {LL ret = 0;for(int i = x; i > 0; i -= Lowbit(i)) {for(int j = y; j > 0; j -= Lowbit(j)) {ret += data[i][j];}}return ret; } void update(int x, int y, int delta) {for(int i = x; i <= Row; i += Lowbit(i)) {for(int j = y; j <= Col; j += Lowbit(j)) {data[i][j] += delta;}} } void work() {char c;int x1, y1, x2, y2, n;scanf(" %c", &c);if(c == 'S') {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);if(x1 > x2) {swap(x1, x2);}if(y1 > y2) {swap(y1, y2);}printf("%d\n", (int)(sum(x2 + 1, y2 + 1) - sum(x1, y2 + 1) + sum(x1, y1) - sum(x2 + 1, y1)));}else if(c == 'A') {scanf("%d%d%d", &x1, &y1, &n);update(x1 + 1, y1 + 1, n);}else if(c == 'D') {scanf("%d%d%d", &x1, &y1, &n);x1++, y1++;int t =sum(x1, y1) - sum(x1 - 1, y1) - sum(x1, y1 - 1) + sum(x1 - 1, y1 - 1);if(t < n) {n = t;}update(x1, y1, -n);}else if(c == 'M') {scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n);x1++, y1++;x2++, y2++;int t =sum(x1, y1) - sum(x1 - 1, y1) - sum(x1, y1 - 1) + sum(x1 - 1, y1 - 1);if(t < n) {n = t;}update(x1, y1, -n);update(x2, y2, n);} } void init() {for(int i = 1; i <= Row; i++) {for(int j = 1; j <= Col; j++) {update(i, j, 1);}} } int main() { #ifndef ONLINE_JUDGEfreopen("data.in", "r", stdin); #endifint T, Q;scanf("%d", &T);for(int t = 1; t <= T; t++) {printf("Case %d:\n", t);scanf("%d", &Q);fill(*data, *data + MAXN * MAXN, 0);init();while(Q--) {work();}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/moonbay/archive/2012/11/01/2749579.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

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

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