Mobile phones--POJ 1195

时间：2010-09-29 来源：勇泽

1、题目类型：模拟、计算几何、树状数组。

2、解题思路：（1）树状数组的经典应用；（2）面积处理过程中，面积=Sum(R,T)-Sum(R,B-1)-Sum(L-1,T)+Sum(L-1,B-1)。

3、注意事项：注意貌似除了树状数组这种方法，其他的方法都TLE，面积处理时候，记得加上减去两次的部分Sum(L-1,B-1)。

4、实现方法:

#include<iostream>
using namespace std;

int N;
int C[1050][1050];

int Lowbit(int x)
{
    return x&(-x);
}

void Modify(int x,int y,int A)
{
    int i,j;
    for(i=x;i<=N;i+=Lowbit(i))
    {
        for(j=y;j<=N;j+=Lowbit(j))
        {
            C[i][j]+=A;
        }
    }
}

int Sum(int x,int y)
{
    int i,j;
    int sum=0;
    for(i=x;i>0;i-=Lowbit(i))
    {
        for(j=y;j>0;j-=Lowbit(j))
        {
            sum+=C[i][j];
        }
    }
    return sum;
}

int GetSum(int L,int B,int R,int T)
{
    return Sum(R,T)-Sum(R,B-1)-Sum(L-1,T)+Sum(L-1,B-1);
}

int main()
{
    int op,X,Y,A;
    int L,B,R,T;
    memset(C,0,sizeof(C));
    cin>>op>>N;
    while(cin>>op && op!=3)
    {
        if(op==1)
        {
            cin>>X>>Y>>A;
            Modify(X+1,Y+1,A);
        }
        else
        {
            cin>>L>>B>>R>>T;
            cout<<GetSum(L+1,B+1,R+1,T+1)<<endl;
        }
    }
    return 0;
}