首页 > 代码库 > POJ1195 Mobile phones

POJ1195 Mobile phones

题解:

二维PUIQ裸题

注意3点

1.在add时,写2个for循环而不是两个while。

2.从0开始,所以全部需要+1

3.在计算sum时,画图模拟一下就知道如何做了

代码:

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100010;const int N=200001000;const int mod=9901;ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}//-----------------------------------------------------------------------------int m[1200][1200],c[1200][1200];int lowbit(int x) {return x&-x;}void add(int x,int y,int v){    for(int i=x;i<1200;i+=lowbit(i))    for(int j=y;j<1200;j+=lowbit(j))    c[i][j]+=v;}ll sum(int x,int y){    ll cnt=0;    for(int i=x;i;i-=lowbit(i))    for(int j=y;j;j-=lowbit(j))    cnt+=c[i][j];    return cnt;}int main(){    int x1,y1,x2,y2,val,op;    while(~scanf("%d",&op)&&op!=3){        if(op==0) scanf("%d",&val);        if(op==1){            scanf("%d%d%d",&x1,&y1,&val);            x1++;y1++;            add(x1,y1,val);        }        if(op==2){            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);            x1++;y1++;x2++;y2++;            printf("%lld\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));        }    }    return 0;}

 

POJ1195 Mobile phones