See you~（HDOJ 1892）
Problem Description
Now I am leaving hust acm. In the past two and half years, I learned so many knowledge about Algorithm and Programming, and I met so many good friends. I want to say sorry to Mr, Yin, I must leave now ~~>.<~~. I am very sorry, we could not advanced to the World Finals last year.
When coming into our training room, a lot of books are in my eyes. And every time the books are moving from one place to another one. Now give you the position of the books at the early of the day. And the moving information of the books the day, your work is to tell me how many books are stayed in some rectangles.
To make the problem easier, we divide the room into different grids and a book can only stayed in one grid. The length and the width of the room are less than 1000. I can move one book from one position to another position, take away one book from a position or bring in one book and put it on one position.
Input
In the first line of the input file there is an Integer T(1<=T<=10), which means the number of test cases in the input file. Then N test cases are followed.
For each test case, in the first line there is an Integer Q(1<Q<=100,000), means the queries of the case. Then followed by Q queries.
There are 4 kind of queries, sum, add, delete and move.
For example:
S x1 y1 x2 y2 means you should tell me the total books of the rectangle used (x1,y1)-(x2,y2) as the diagonal, including the two points.
A x1 y1 n1 means I put n1 books on the position (x1,y1)
D x1 y1 n1 means I move away n1 books on the position (x1,y1), if less than n1 books at that position, move away all of them.
M x1 y1 x2 y2 n1 means you move n1 books from (x1,y1) to (x2,y2), if less than n1 books at that position, move away all of them.
Make sure that at first, there is one book on every grid and 0<=x1,y1,x2,y2<=1000,1<=n1<=100.
Output
At the beginning of each case, output "Case X:" where X is the index of the test case, then followed by the "S" queries.
For each "S" query, just print out the total number of books in that area.
Sample Input
2 3 S 1 1 1 1 A 1 1 2 S 1 1 1 1 3 S 1 1 1 1 A 1 1 2 S 1 1 1 2
Sample Output
Case 1: 1 3 Case 2: 1 4
My Code
会二维树状数组的话，除了一些小坑，还是比较简单的。
第一个点，搬走书或者移动书的时候要判断是否超过原有的书。
第二个点，求和的时候，给你的第一个点不一定是在第二个点的左上角，需要处理一下。
第三个点，矩阵是左上角是(0,0)不是(1,1)所以最好所有坐标加1（加1的话，右下角就可能到(1001,1001)，也要注意一下）
#include
#include
#include
#include
using namespace std;
int t;
int cnt;
int a[1005][1005]; //二维树状数组
int b[1005][1005]; //普通数组，存每个点的书的数量
int n;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int y, int v)
{
int j;
b[x][y] += v;
while (x < 1005)
{
j = y;
while (j < 1005)
{
a[x][j] += v;
j += lowbit(j);
}
x += lowbit(x);
}
}
int sub(int x, int y, int v)
{
if (b[x][y] < v) //如果超过原有的书，就搬完原有的书
v = b[x][y];
b[x][y] -= v;
int j;
while (x < 1005)
{
j = y;
while (j < 1005)
{
a[x][j] -= v;
j += lowbit(j);
}
x += lowbit(x);
}
return v; //返回实际搬运的书的数量
}
int sum1(int x, int y) //sum1(x,y)为以(1,1)-(x,y)为对角线的矩阵的元素和
{
int ans = 0;
int j;
while (x > 0)
{
j = y;
while (j > 0)
{
ans += a[x][j];
j -= lowbit(j);
}
x -= lowbit(x);
}
return ans;
}
int sum2(int x1, int y1, int x2, int y2)
{
if (x1 > x2)
swap(x1, x2); //点(x1,y1)不一定在(x2,y2)的左上角，所以要交换一下
if (y1 > y2)
swap(y1, y2);
return sum1(x2, y2) - sum1(x2, y1 - 1) - sum1(x1 - 1, y2) + sum1(x1 - 1, y1 - 1);
}
int main()
{
cin >> t;
while (t--)
{
cin >> n;
memset(a, 0, sizeof(a));
for (int i = 1; i < 1005; i++) //树状数组最好从1开始，否则会大大降低效率
for (int j = 1; j < 1005; j++)
{
add(i, j, 1);
b[i][j] = 1;
}
cout << "Case " << ++cnt << ":" << endl;
for (int i = 0; i < n; i++)
{
char c;
cin >> c;
if (c == 'S')
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1++; //因为数据是有(0,0)点，所以所有坐标加1
y1++;
x2++;
y2++;
cout << sum2(x1, y1, x2, y2) << endl;
}
else if (c == 'A')
{
int x, y, v;
cin >> x >> y >> v;
x++;
y++;
add(x, y, v);
}
else if (c == 'D')
{
int x, y, v;
cin >> x >> y >> v;
x++;
y++;
sub(x, y, v);
}
else
{
int x1, y1, x2, y2, v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
x1++;
y1++;
x2++;
y2++;
v = sub(x1, y1, v);
add(x2, y2, v);
}
}
}
return 0;
} 
OωO
