HDU 1892-See you（二维BIT）

题意：

最多1000*1000的方格，各方格开始有一本书

有四种操作：对指定方格把书拿走或向里面放书，从一个方格那一定量的书放到另一个方格，查询给定对角线顶点的坐标的矩形范围内包含的书的总数

分析：

二维BIT，注意方格的书数小于拿书数量的情况

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define N 1010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int sum[N][N],n,a[N][N];

int lowbit(int x){

    return (x)&(-x);

}

void add(int x,int y,int v){

    for(int i=x;i<N;i+=lowbit(i))

    for(int j=y;j<N;j+=lowbit(j)){

        sum[i][j]+=v;

    }

}

int sum1(int x,int y){

    int num=;

    for(int i=x;i>;i-=lowbit(i))

        for(int j=y;j>;j-=lowbit(j))

        num+=sum[i][j];

    return num;

}

int main()

{

int t,test=;

    char op[];

    int x1,x2,y1,y2,v,q;

    scanf("%d",&t);

    while(t--){

            memset(sum,,sizeof(sum));

       for(int i=;i<N;++i)

       for(int j=;j<N;++j){

        a[i][j]=;

        add(i,j,);

       }

        printf("Case %d:\n",++test);

        scanf("%d",&q);

        while(q--){

            scanf("%s",op);

            if(op[]=='S'){

                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

                int sx=min(x1,x2);

                int ex=max(x1,x2);

                int sy=min(y1,y2);

                int ey=max(y1,y2);

                sx++;ex++;

                sy++;ey++;

                int tmp=sum1(ex,ey)-sum1(sx-,ey)-sum1(ex,sy-)+sum1(sx-,sy-);

                printf("%d\n",tmp);

            }

            else if(op[]=='A'){

                scanf("%d%d%d",&x1,&y1,&v);

                x1++;

                y1++;

                add(x1,y1,v);

                a[x1][y1]+=v;

            }

            else if(op[]=='D'){

            scanf("%d%d%d",&x1,&y1,&v);

            x1++;

            y1++;

            if(v>a[x1][y1])v=a[x1][y1];

            add(x1,y1,-v);

            a[x1][y1]-=v;

            }

            else if(op[]=='M'){

                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);

                x1++;y1++;

                x2++;y2++;

                if(a[x1][y1]<v)

                    v=a[x1][y1];

                add(x1,y1,-v);

                add(x2,y2,v);

                a[x1][y1]-=v;

                a[x2][y2]+=v;

            }

        }

    }

return ;

}