【POJ1195】【二维树状数组】Mobile phones

时间:2022-06-07 20:38:43

Description

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

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 input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table. 
【POJ1195】【二维树状数组】Mobile phones
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

Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard 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的更多相关文章

  1. POJ1195&lpar;二维树状数组&rpar;

    Mobile phones Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 17176   Accepted: 7920 De ...

  2. poj1195二维树状数组模板

    二维树状数组和一维的也差不多,改一下add和query函数即可:即按行修改,行内单点修改即可 /* 二维树状数组,询问一个二维区间内的数之和 */ #include<iostream> # ...

  3. 【poj1195】Mobile phones&lpar;二维树状数组&rpar;

    题目链接:http://poj.org/problem?id=1195 [题意] 给出一个全0的矩阵,然后一些操作 0 S:初始化矩阵,维数是S*S,值全为0,这个操作只有最开始出现一次 1 X Y ...

  4. poj 1195&colon;Mobile phones(二维树状数组,矩阵求和)

    Mobile phones Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 14489   Accepted: 6735 De ...

  5. &lpar;简单&rpar; POJ 1195 Mobile phones,二维树状数组。

    Description Suppose that the fourth generation mobile phone base stations in the Tampere area operat ...

  6. POJ 1195 Mobile phones (二维树状数组)

    Description Suppose that the fourth generation mobile phone base stations in the Tampere area operat ...

  7. POJ 1195:Mobile phones 二维树状数组

    Mobile phones Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 16893   Accepted: 7789 De ...

  8. POJ-1195 Mobile phones---裸的二维树状数组(注意下标从1,1开始)

    题目链接: https://vjudge.net/problem/POJ-1195 题目大意: 直接维护二维树状数组 注意横纵坐标全部需要加1,因为树状数组从(1,1)开始 #include<c ...

  9. POJ 1195 Mobile phones【二维树状数组】

    <题目链接> 题目大意: 一个由数字构成的大矩阵,开始是全0,能进行两种操作1) 对矩阵里的某个数加上一个整数(可正可负)2) 查询某个子矩阵里所有数字的和要求对每次查询,输出结果 解题分 ...

随机推荐

  1. navicat注册码

    1. navicat for mysql 9 注册码   :::   NAVL-EHNC-7N7P-W6GM  2. navicat for mysql 9.17中文版 注册码 :: NAVM-5ZC ...

  2. MongoDB 优化器MongoDB Database Profiler(12)

    优化器profile 在MySQL 中,慢查询日志是经常作为我们优化数据库的依据,那在MongoDB 中是否有类似的功能呢?答案是肯定的,那就是MongoDB Database Profiler. 1 ...

  3. Xpath定位大全

    selenium使用Xpath定位之完整篇   其中有一片文章提到了xpath元素定位,但是该文章中有些并不能适应一些特殊与个性化的场景.在文本中提供xpath元素的定位终极篇,你一定能在这里找到你需 ...

  4. 想使用 MongoDB ,你应该了解这8个方面!

    应用性能高低依赖于数据库性能,MongoDB 是一个基于分布式文件存储的数据库.由 C++ 语言编写,旨在为 WEB 应用提供可扩展的高性能数据存储解决方案.MongoDB 是一个介于关系数据库和非关 ...

  5. ALTER---为已创建的表添加默认值

    alter table table_name modify column_name default default_value; 例: alter table userinfo modify emai ...

  6. HDU 1423 Greatest Common Increasing Subsequence&lpar;最长公共上升LCIS&rpar;

    HDU 1423 Greatest Common Increasing Subsequence(最长公共上升LCIS) http://acm.hdu.edu.cn/showproblem.php?pi ...

  7. 求Sn&equals;a&plus;aa&plus;aaa&plus;…&plus;aa…aaa(有n个a)…

    时间限制: 1 Sec  内存限制: 128 MB 提交: 352  解决: 174 [提交][状态][讨论版] 题目描述 求Sn=a+aa+aaa+-+aa-aaa(有n个a)之值,其中a是一个数字 ...

  8. python web入门程序

    python2.x web入门程序 #!/usr/bin/python # -*- coding: UTF-8 -*- # 只在python2.x 有效 import os #Python的标准库中的 ...

  9. 自学Linux Shell12&period;6-嵌套循环for命令

    点击返回 自学Linux命令行与Shell脚本之路 12.6-嵌套循环for命令 嵌套循环就是在一个循环中还有一个循环. 内部循环在外部循环体中,在外部循环的每次执行过程中都会触发内部循环,直到内部循 ...

  10. Java面试中遇到的坑【填坑篇】

    看到大家对上篇<Java面试中遇到的坑>一文表现出强力的关注度,说明大家确实在面试中遇到了类似的难题.大家在文章留言处积极留言探讨面试中遇到的问题,其中几位同学还提出了自己的见解,我感到非 ...