矩阵:频繁翻转一个二进制矩阵,求任一点值。
3.3活用各种数据结构
Binary Indexed Tree
好久没刷题了,感觉智商跌了一半。这道题是二维的Range Sum Query,直接用二维的BIT太慢。在一维POJ 3109 Inner Vertices的基础上,拓展到二维即可。一维用了2个BIT,二维得用4个2维的BIT。它们满足sum(y,x)=bit_xy(y,x)*yx + bit_y(y,x)*y + bit_x(y,x)*x + bit(y,x),如果有好用的模板的话,这题就相当轻松了。
如图所示:
每个2DBIT可以高效地更改某一点的值以及求出区域和,但是无法高效地修改一个区域的值。这时在每个维度上使用2个BIT记录初始值和修正值,控制复杂度于O(X×T×logN×logN)。
#include <iostream> using namespace std; #define MAX_N 1000 + 1 typedef long long bit_t; // 二维矩阵的区间和 struct BinaryIndexedTree2D { #define MAX_BIT MAX_N + 1 bit_t data[MAX_BIT][MAX_BIT]; int size; void init(int size) { memset(data, 0, sizeof(data)); this->size = size; } // 求(0,0) 到(x,y)围成的矩形区域元素之和 bit_t sum(int y, int x) { bit_t ret = 0; for (int ty = y; ty; ty -= ty&-ty) { for (int tx = x; tx; tx -= tx&-tx) { ret += data[ty][tx]; } } return ret; } // 执行(x,y) += v void add(int y, int x, bit_t v) { for (int ty = y + 1; ty <= size; ty += ty&-ty) { for (int tx = x + 1; tx <= size; tx += tx&-tx) { data[ty][tx] += v; } } } }; BinaryIndexedTree2D bit_xy, bit_x, bit_y, bit; // sum(y,x)=bit_xy(y,x)*yx + bit_y(y,x)*y + bit_x(y,x)*x + bit(y,x) //矩形[y1, y2) * [x1, x2)区域内每个元素增加v void add(int y1, int y2, int x1, int x2, bit_t v) { bit_xy.add(y1, x1, v); bit_xy.add(y1, x2, -v); bit_xy.add(y2, x1, -v); bit_xy.add(y2, x2, v); bit_x.add(y1, x1, -y1 * v); bit_x.add(y1, x2, y1 * v); bit_x.add(y2, x1, y2 * v); bit_x.add(y2, x2, -y2 * v); bit_y.add(y1, x1, -x1 * v); bit_y.add(y1, x2, x2 * v); bit_y.add(y2, x1, x1 * v); bit_y.add(y2, x2, -x2 * v); bit.add(y1, x1, y1 * x1 * v); bit.add(y1, x2, -x2 * y1 * v); bit.add(y2, x1, -y2 * x1 * v); bit.add(y2, x2, y2 * x2 * v); } // 区域和 bit_t sum(int y, int x) { return bit_xy.sum(y, x) * y * x + bit_x.sum(y, x) * x + bit_y.sum(y, x) * y + bit.sum(y, x); } // 区域和,左开右闭 bit_t sum(int y1, int y2, int x1, int x2) { return sum(y1, x1) + sum(y2, x2) - (sum(y1, x2) + sum(y2, x1)); } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int X; scanf("%d", &X); while (X--) { int N, T; scanf("%d%d", &N, &T); bit.init(N); bit_x.init(N); bit_y.init(N); bit_xy.init(N); while (T--) { char cmd; scanf(" %c", &cmd); if (cmd == 'C') { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); add(y1 - 1, y2, x1 - 1, x2, 1); } else { int x, y; scanf("%d%d", &x, &y); printf("%d\n", (sum(y - 1, y, x - 1, x) & 1)); } } puts(""); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
13029281 | hankcs | 2155 | Accepted | 31596K | 2610MS | C++ | 2565B | 2014-07-05 17:02:50 |
您是搞ACM 的吗?
不是,我是个业余爱好者。