鏈接：http://poj.org/problem?id=1195

Mobile phones

Time Limit: 5000MS	?	Memory Limit: 65536K
Total Submissions: 16646	?	Accepted: 7653

Description

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.

Input

The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table.?
The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3.

Table size: 1 * 1 <= S * S <= 1024 * 1024
Cell value V at any time: 0 <= V <= 32767
Update amount: -32768 <= A <= 32767
No of instructions in input: 3 <= U <= 60002
Maximum number of phones in the whole table: M= 2^30?

Output

Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard output.

Sample Input

0 4 1 1 2 3 2 0 0 2 2 1 1 1 2 1 1 2 -1 2 1 1 2 3 3

Sample Output

3 4

Source

IOI 2001

大意——給你一個n*n矩陣的區域，它的行列下標都是從0開始的。每一個矩陣元素代表一個基站。基站內的處于執行中的手機數量由于各種原因會不斷變化。各個基站會不定期地向主基站報告，以便統計執行中的手機數量。你的任務是依據對應的命令完畢對應的操作。

當中基本的就是更新某一個矩陣元素的值和一個區域的矩陣元素值之和。

思路——非常顯然這是一個裸的二維樹狀數組的題。

其操作就是更新某一個值和區間求和。因此。我們直接用一維樹狀數組推廣過來就可以解決這個問題。注意：矩陣元素下標從0開始。

復雜度分析——時間復雜度:O((log(n))^2),空間復雜度:O(n^2)

附上AC代碼：

#include <iostream> #include <cstdio> #include <string> #include <cmath> #include <iomanip> #include <ctime> #include <climits> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <set> #include <map> //#pragma comment(linker, "/STACK:102400000, 102400000") using namespace std; typedef unsigned int li; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const double pi = acos(-1.0); const double e = exp(1.0); const double eps = 1e-8; const int maxn = 1030; int mat[maxn][maxn]; int order; // 鍵入命令 int n; // 數組大小int lowbit(int x); // 求2^k,k表示x為二進制時末尾的零的個數 void update(int x, int y, int add); // 更新狀態 int sum(int x, int y); // 求和int main() {ios::sync_with_stdio(false);int x1, y1, x2, y2, add, ans;while (scanf("%d", &order)==1 && 3!=order){switch(order){case 0:scanf("%d", &n);memset(mat, 0, sizeof(mat)); // 初始化為0break;case 1:scanf("%d%d%d", &x1, &y1, &add);update(x1+1, y1+1, add); // x，y可能為0，所以加1。后面相似break;case 2:scanf("%d%d%d%d", &x1, &y1, &x2, &y2);ans = 0;ans += sum(x2+1, y2+1); // 總求和ans -= sum(x2+1, y1);ans -= sum(x1, y2+1); // 去掉多余部分ans += sum(x1, y1); // 多減掉一部分，加回來。繪圖可知printf("%d\n", ans);break;default:printf("INPUT ERROR!\n");break;}}return 0; }int lowbit(int x) {return (x&(-x)); }void update(int x, int y, int add) { // x，y表示矩陣下標，此功能是把下標為x。y的數加上addfor (int i=x; i!=0&&i<=n; i+=lowbit(i))for (int j=y; j!=0&&j<=n; j+=lowbit(j))mat[i][j] += add; }int sum(int x, int y) { // x。y表示矩陣下標，此功能是把下標小于x，y的矩陣元素值加起來int res = 0;for (int i=x; i>0; i-=lowbit(i))for (int j=y; j>0; j-=lowbit(j))res += mat[i][j];return res; }

總結

以上是生活随笔為你收集整理的POJ 1195 Mobile phones的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。