POJ 1195 Mobile phones

Mobile phones
http://poj.org/problem?id=1195
Time Limit：5000 MS
 
メモリLimit：65536 K
Total Submissions：11696
 
Acceepted:5369
Description
Suppose that the fourth generation mobile phone base statins in the Tampere ara operaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaoperaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa phone is moved from aスクウェアto another or a phone is switch on or off.At times，each base station reportthe change in the number of active phons to the mation along with the column of the matix.
Write a program、which receives these reportand answers queries about the current total number of active mobile phones in any rectanle-sharped ara.
Input
The input is read from standand input as integers and the answers to the queries are written to standard output as integers.The input is encoded as.Each input codent corate a separate line ingone.The of stration
The values will always be in range、so there isのneed to check them.In particular、if A is negative、it can be asumed that it will not reduce the square value below zero.The indexing starts at 0、e.fore 3。
Table size:1*1<=S*S<=1024*1024
Celvalue V at any time:0<=V==32767 Update amount:-32768<=A==32767 No of instructions in input:3<=U==60.02
Maximumber of phones in the whole table:M=2^30
Output
Your program shound not answer anything to linears with an instruction other than 2.If the instruction is 2，then your program is expected to answer the query by writing the answers a singline ingline.ingland.ingtaingtaingtaingtaingtaingtaingtanter.ingtaingtanter.ingtaingtantingtantingtanter.ing
Sample Input

0 4

1 1 2 3

2 0 0 2 2 

1 1 1 2

1 1 2 -1

2 1 1 2 3 

3

Sample Output

3

4

ソurce
IOI 2001
 
2、問題を解く構想：題意、与えられたn＊n行列といくつかのオンライン操作は、ある一点（x，y）の値に対して修正し、長方形（x 1，y 1，x 2，y 2）の要素とを調べます。ステップ、（1）樹状配列の古典的応用。（2）面積処理中、面積=Sum(R，T)-Sum(R，B-1)-Sum(L-1,T)+Sum(L-1,B-1)です。
3、注意事項：樹状配列を除く他の方法はTLEとなりますが、面積処理の際には、2回差し引いた部分Sum（L-1，B-1）を加えてください。
 

#include<iostream>

#include<cstdio>



using namespace std;



int N,c[1050][1050];



int lowbit(int x){

    return x&(-x);

}



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+=c[i][j];

    return sum;

}



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

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

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

            c[i][j]+=val;

}



int main(){

    int op;

    int x,y,a;

    int l,b,r,t;

    scanf("%d%d",&op,&N);

    while(scanf("%d",&op) && op!=3){

        if(op==1){

            scanf("%d%d%d",&x,&y,&a);

            update(x+1,y+1,a);

        }else if(op==2){

            scanf("%d%d%d%d",&l,&b,&r,&t);

            int ans=Sum(r+1,t+1)-Sum(r+1,b)-Sum(l,t+1)+Sum(l,b);

            printf("%d
",ans);

        }

    }

    return 0;

}