[poj2155]Matrix(二维树状数组)
Matrix
Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 25004 | Accepted: 9261 |
Description
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.
Output
There is a blank line between every two continuous test cases.
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
Source
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int bit[][];
int n;
int lb(int x){
return x&(-x);
}
int q(int x,int y){
int ans=;
while(x){
int i=y;
while(i){
ans+=bit[x][i];
i-=lb(i);
}
x-=lb(x);
}
return ans%;
}
int c(int x,int y){
while(x<=n+){
int i=y;
while(i<=n+){
bit[x][i]++;
i+=lb(i);
}
x+=lb(x);
}
return ;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int t;
scanf("%d %d",&n,&t);
memset(bit,,sizeof(bit));
for(int i=;i<=t;i++){
char op=getchar();
while(op!='C'&&op!='Q')op=getchar();
switch(op){
case 'C':
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
c(x1,y1);
c(x2+,y1);
c(x1,y2+);
c(x2+,y2+);
break;
case 'Q':
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",q(x,y));
break;
default:
break;
}
}
puts("");
}
return ;
}
最新文章
- Swift与OC混编
- 在不格式化原有系统盘的情况下,利用grub4dos+firadisk制作RamOS VHD Win7总结
- POJ 1742 Coins DP 01背包
- ArcGis 获取地理、平面坐标系
- JNI-入门之二
- 一段网上java常见escape和unescape方法的BUG
- setTimeout 虚假的“异步”
- BZOJ 1787: [Ahoi2008]Meet 紧急集合( 树链剖分 )
- 通用mapper的使用
- 【webpack】-- 自动刷新
- Apache的作用及意义
- poj 2762 强连通缩点+拓扑排序
- git笔记------自己学习git的心得
- 通过C#来开启、关闭、重启Windows服务
- Excel读写
- was系统的远程调试
- 【python 网络爬虫】之scrapy系列
- 关于表单----html杂记
- 01-Linux的基本指令
- Windows下SVN备份脚本
热门文章
- Python强化训练笔记(一)——在列表,字典,集合中筛选数据
- asp.net identity 2.2.0 中角色启用和基本使用(七)提示点
- 封装常用的js(Base.js)——【01】理解库,获取节点,连缀,
- NEC学习 ---- 布局 -三列, 左右定宽,中间自适应
- UIBezierPath类 笔记
- 蓝牙—RFCOMM协议
- iOS/OS X线程安全的基础知识
- java 8 新特性
- 三维高斯模型 opencv实现
- 本图片处理类功能非常之强大可以实现几乎所有WEB开发中对图像的处理功能都集成了,包括有缩放图像、切割图像、图像类型转换、彩色转黑白、文字水印、图片水印等功能