首页 > ACM题库 > HDU-杭电 > HDU 1892 See you~-树状数组-[解题报告] C++
2013
12-23

HDU 1892 See you~-树状数组-[解题报告] C++

See you~

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

Case 1:
1
3
Case 2:
1
4

四个操作:

1、S X1 Y1  X2 Y2 输出[x1 y1 x2 y2]矩阵的和。

2、A X1 Y1 N1 点[X1,Y1]的值加N1 。

3、D X1 Y1 N1 点[X1,Y1]的值减小N1,不足N1减为0。

4、M X1 Y1 X2 Y2 N1 将[X1,Y1]的值移动N1到[X2,Y2] ,不足则全部移动。

算法:二维树状数组

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 2000000000
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void RD(int &ret)
{
    char c;
    do
    {
        c = getchar();
    }
    while(c < '0' || c > '9');
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}
int lowbit(int x )
{
    return x & (-x) ;
}
int n , m ;
int a[1005][1005] ;
void add(int x ,int y ,int num)
{
    for (int i = x ;i <= n ;i += lowbit(i))
    {
        for (int j = y ; j <= m ;j += lowbit(j) )
        {
            a[i][j] += num ;
        }
    }
}
int sum(int x ,int y )
{
    int ans = 0 ;
    for (int i = x ;i > 0 ;i -= lowbit(i))
    {
        for (int j = y ;j > 0 ; j -= lowbit(j))
        ans += a[i][j] ;
    }
    return ans ;
}
int getsum(int x1, int y1, int x2 ,int y2)
{
    return sum(x2,y2) + sum(x1 - 1,y1 - 1) - sum(x1 - 1,y2) - sum(x2,y1 - 1) ;
}
int getsum(int x1 ,int y1)
{
    return sum(x1,y1) - sum(x1,y1 - 1) - sum(x1 - 1 ,y1) + sum(x1 - 1 , y1 - 1 ) ;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("acm.txt", "r", stdin);
#endif
    int T ;
    RD(T) ;
    int cc = 0 ;
    while(T -- )
    {
        int cas ;
        RD(cas) ;
        n = 1004 , m = 1004  ;
        mem(a,0) ;
        printf("Case %d:\n",++cc) ;
        REP(i,1,n)REP(j,1,m){
            add(i,j,1) ;
        }
        while(cas -- )
        {
            char op ;
            op = getchar() ;
            if(op == 'S')
            {
                int x1 ,y1, x2 ,y2 ;
                RD(x1) ; RD(y1) ;RD(x2) ;RD(y2) ;
                x1 ++ ,y1 ++ ,x2 ++ ,y2 ++ ;//因为X1,X2,Y1,Y2是从0开始的。
                if(x1 > x2)swap(x1,x2) ;//注意X2,Y2不一定比X1,Y1大,这是个坑。
                if(y1 > y2)swap(y1,y2) ;
                printf("%d\n",getsum(x1,y1,x2,y2)) ;
            }
            else if(op == 'A')
            {
                int x1 ,y1 ,num ;
                RD(x1) ;RD(y1) ;RD(num) ;
                x1 ++ ,y1 ++ ;
                add(x1,y1,num) ;
            }
            else if(op == 'D')
            {
                int x1 ,y1 ,num ;
                RD(x1) ;RD(y1) ;RD(num) ;
                x1 ++ ,y1 ++ ;
                int num1 = getsum(x1,y1) ;
                if(num1 >= num)
                add(x1,y1,-num) ;
                else
                add(x1,y1,-num1) ;
            }
            else if(op == 'M')
            {
                int x1 ,y1 ,x2, y2 ,num ;
                RD(x1) ; RD(y1) ;RD(x2) ;RD(y2) ;RD(num) ;
                x1 ++ ,y1 ++ ,x2 ++ ,y2 ++ ;
                int num1 = getsum(x1,y1) ;
                if(num1 >= num )
                {
                    add(x1,y1,-num ) ;
                    add(x2,y2,num) ;
                }
                else
                {
                    add(x1,y1,-num1) ;
                    add(x2,y2,num1) ;

                }
            }
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/just_water/article/details/9107447


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.