本文主要是介绍poj 1195 Mobile phones,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:点击打开链接
Description
Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.
Input
The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3.
Table size: 1 * 1 <= S * S <= 1024 * 1024
Cell value V at any time: 0 <= V <= 32767
Update amount: -32768 <= A <= 32767
No of instructions in input: 3 <= U <= 60002
Maximum number of phones in the whole table: M= 2^30
Output
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题目大意:在一个二维的矩形内,每个点表示该处的手机数量,初始化为0。有修改和查询两种操作,修改是该点的值,查询是查两个点之间的矩形内的手机数量
ps:这个题一开始做的挺快的,读题太粗滤,导致wa3次,直接就对两个点之间的差进行相减求和了,起始不然。
这是一个二维的树状数组,当然了也可以是二维的线段树做,但我现在还不会二维线段树,毕竟二维树状数组写起来简单,蛋真正的理解深刻了真的挺难得,现在的我只是在回用的阶段,多少的能明白他的意思。。。
#include <iostream>
#include<cstdio>
#include<cstring>using namespace std;long long c[1500][1500];
int n;int lowbit(int x)
{return x&(-x);
}void add(int x,int y,int val)
{while(x<=n){int y1=y;while(y1<=n){c[x][y1]=c[x][y1]+val;y1+=lowbit(y1);}x+=lowbit(x);}
}long long Sum(int x,int y)
{int sum=0;while(x>0){int y1=y;while(y1>0){sum+=c[x][y1];y1-=lowbit(y1);}x-=lowbit(x);}return sum;
}
int main()
{int id;int x,y,a;int l,b,r,t;memset(c,0,sizeof(c));while(scanf("%d",&id)){if(id==0){scanf("%d",&n);memset(c,0,sizeof(c));}else if(id==3)break;else if(id==1){scanf("%d%d%d",&x,&y,&a);add(x+1,y+1,a);}else if(id==2){scanf("%d%d%d%d",&l,&b,&r,&t);printf("%lld\n",Sum(r+1,t+1)+Sum(l,b)-Sum(r+1,b)-Sum(l,t+1));}}return 0;
}
这篇关于poj 1195 Mobile phones的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!