HDU 1892 See you~

http://acm.hdu.edu.cn/showproblem.php?pid=1892
2 Dツリー配列で、裸です...


View Code

#include <iostream>

#include <algorithm> 

#include <cstring>

using namespace std;

const int MAX=1010;

int weight[MAX][MAX],tree[MAX][MAX];

int lowbit(int i){

    return i&(-i);

}

void update(int x,int y,int val)

{

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

        for(int j=y;j<MAX;j+=lowbit(j))

            tree[i][j]+=val;

}

int Sum(int x,int y)

{

    int sum=0;

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

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

            sum+=tree[i][j];

    return sum;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int cas=1;cas<=T;cas++)

    {

        memset(tree,0,sizeof(tree));

        for(int i=1;i<MAX;i++)

            for(int j=1;j<MAX;j++)

            {

                update(i,j,1);

                weight[i][j]=1;

            }

        //weight[0][0]=0;

        int n;

        scanf("%d",&n);

        printf("Case %d:
",cas);

        while(n--)

        {

            char op[2];

            scanf("%s",op);

            int x1,y1,x2,y2;

            int n1;

            switch(op[0])

            {

                case 'S':

                {

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

                    x1++;y1++;x2++;y2++;

                    int minx,miny,maxx,maxy;

                    minx=min(x1,x2);

                    miny=min(y1,y2);

                    maxx=max(x1,x2);

                    maxy=max(y1,y2);

                    printf("%d
",Sum(maxx,maxy)-Sum(minx-1,maxy)-Sum(maxx,miny-1)+Sum(minx-1,miny-1));    

                    break;

                }

                case 'A':

                {

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

                    x1++;y1++;

                    update(x1,y1,n1);

                    weight[x1][y1]+=n1;

                    break;

                }

                case 'D':

                {

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

                    x1++;y1++;

                    if(weight[x1][y1]<=n1)

                    {

                        update(x1,y1,-weight[x1][y1]);

                        weight[x1][y1]=0;

                    }

                    else

                    {

                        update(x1,y1,-n1);

                        weight[x1][y1]-=n1;

                    }

                    break;

                }

                case 'M':

                {

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

                    x1++;y1++;x2++;y2++;

                    if(weight[x1][y1]<=n1)

                    {

                        update(x1,y1,-weight[x1][y1]);

                        update(x2,y2,weight[x1][y1]);

                        weight[x2][y2]+=weight[x1][y1];

                        weight[x1][y1]=0;

                    }

                    else

                    {

                        update(x1,y1,-n1);

                        update(x2,y2,n1);

                        weight[x1][y1]-=n1;

                        weight[x2][y2]+=n1;

                    }

                    break;

                }

            }

        }

    }

    return 0;

}