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
【分析】
不说了,最基本的二维树状数组
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <map> const int MAXN = * + ;
const int N=;
using namespace std; int n, array[N][N]; int lowbit(int x){return x & (-x);}
void add(int i, int j, int w) {
int tmp;
while(i <= n){
tmp=j;
while(tmp <= n){
array[i][tmp] += w;
tmp += lowbit(tmp);
}
i += lowbit(i);
}
} int sum(int i, int j){
int tmp, ans=;
while(i > ){
tmp=j;
while(tmp > ){
ans += array[i][tmp];
tmp -= lowbit(tmp);
}
i -= lowbit(i);
}
return ans;
} int main(){
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int op, x1, y1, x2, y2, w;
memset(array, , sizeof(array));
while( ~scanf("%d", &op) ){
if(op == ){
scanf("%d", &n);
n++;
}else if(op == ){
scanf("%d%d%d", &x1, &y1, &w);
add(x1 + , y1 + , w);
}else if(op == ){
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans=sum(x2 + , y2 + ) - sum(x1, y2 + ) - sum(x2 + , y1) + sum(x1, y1);
printf("%d\n", ans);
}else if(op == )
break;
}
return ;
}
【POJ1195】【二维树状数组】Mobile phones的更多相关文章
-
POJ1195(二维树状数组)
Mobile phones Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 17176 Accepted: 7920 De ...
-
poj1195二维树状数组模板
二维树状数组和一维的也差不多,改一下add和query函数即可:即按行修改,行内单点修改即可 /* 二维树状数组,询问一个二维区间内的数之和 */ #include<iostream> # ...
-
【poj1195】Mobile phones(二维树状数组)
题目链接:http://poj.org/problem?id=1195 [题意] 给出一个全0的矩阵,然后一些操作 0 S:初始化矩阵,维数是S*S,值全为0,这个操作只有最开始出现一次 1 X Y ...
-
poj 1195:Mobile phones(二维树状数组,矩阵求和)
Mobile phones Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 14489 Accepted: 6735 De ...
-
(简单) POJ 1195 Mobile phones,二维树状数组。
Description Suppose that the fourth generation mobile phone base stations in the Tampere area operat ...
-
POJ 1195 Mobile phones (二维树状数组)
Description Suppose that the fourth generation mobile phone base stations in the Tampere area operat ...
-
POJ 1195:Mobile phones 二维树状数组
Mobile phones Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 16893 Accepted: 7789 De ...
-
POJ-1195 Mobile phones---裸的二维树状数组(注意下标从1,1开始)
题目链接: https://vjudge.net/problem/POJ-1195 题目大意: 直接维护二维树状数组 注意横纵坐标全部需要加1,因为树状数组从(1,1)开始 #include<c ...
-
POJ 1195 Mobile phones【二维树状数组】
<题目链接> 题目大意: 一个由数字构成的大矩阵,开始是全0,能进行两种操作1) 对矩阵里的某个数加上一个整数(可正可负)2) 查询某个子矩阵里所有数字的和要求对每次查询,输出结果 解题分 ...
随机推荐
-
navicat注册码
1. navicat for mysql 9 注册码 ::: NAVL-EHNC-7N7P-W6GM 2. navicat for mysql 9.17中文版 注册码 :: NAVM-5ZC ...
-
MongoDB 优化器MongoDB Database Profiler(12)
优化器profile 在MySQL 中,慢查询日志是经常作为我们优化数据库的依据,那在MongoDB 中是否有类似的功能呢?答案是肯定的,那就是MongoDB Database Profiler. 1 ...
-
Xpath定位大全
selenium使用Xpath定位之完整篇 其中有一片文章提到了xpath元素定位,但是该文章中有些并不能适应一些特殊与个性化的场景.在文本中提供xpath元素的定位终极篇,你一定能在这里找到你需 ...
-
想使用 MongoDB ,你应该了解这8个方面!
应用性能高低依赖于数据库性能,MongoDB 是一个基于分布式文件存储的数据库.由 C++ 语言编写,旨在为 WEB 应用提供可扩展的高性能数据存储解决方案.MongoDB 是一个介于关系数据库和非关 ...
-
ALTER---为已创建的表添加默认值
alter table table_name modify column_name default default_value; 例: alter table userinfo modify emai ...
-
HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS)
HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS) http://acm.hdu.edu.cn/showproblem.php?pi ...
-
求Sn=a+aa+aaa+…+aa…aaa(有n个a)…
时间限制: 1 Sec 内存限制: 128 MB 提交: 352 解决: 174 [提交][状态][讨论版] 题目描述 求Sn=a+aa+aaa+-+aa-aaa(有n个a)之值,其中a是一个数字 ...
-
python web入门程序
python2.x web入门程序 #!/usr/bin/python # -*- coding: UTF-8 -*- # 只在python2.x 有效 import os #Python的标准库中的 ...
-
自学Linux Shell12.6-嵌套循环for命令
点击返回 自学Linux命令行与Shell脚本之路 12.6-嵌套循环for命令 嵌套循环就是在一个循环中还有一个循环. 内部循环在外部循环体中,在外部循环的每次执行过程中都会触发内部循环,直到内部循 ...
-
Java面试中遇到的坑【填坑篇】
看到大家对上篇<Java面试中遇到的坑>一文表现出强力的关注度,说明大家确实在面试中遇到了类似的难题.大家在文章留言处积极留言探讨面试中遇到的问题,其中几位同学还提出了自己的见解,我感到非 ...