POJ 2155 Matrix【二维线段树】
题目大意:给你一个全是0的N*N矩阵,每次有两种操作:1将矩阵中一个子矩阵置反,2.查询某个点是0还是1
思路:裸的二维线段树
#include<iostream>
#include<cstdio>
#include <math.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define MOD 1000003
#define maxn 4009
#define LL long long
using namespace std;
int n,num;
bool tree[maxn][maxn];
void add_y(int xx,int node,int l,int r,int ql,int qr)
{
if(ql<=l && r<=qr){tree[xx][node]^=1;return ;}
int mid=(l+r)>>1;
if(ql<mid)add_y(xx,node*2,l,mid,ql,qr);
if(qr>mid)add_y(xx,node*2+1,mid,r,ql,qr);
}
void add_x(int node,int l,int r,int ql,int qr,int y1,int y2)
{
if(ql<=l && r<=qr){add_y(node,1,1,n+1,y1,y2);return ;}
int mid=(l+r)>>1;
if(ql<mid)add_x(node*2,l,mid,ql,qr,y1,y2);
if(qr>mid)add_x(node*2+1,mid,r,ql,qr,y1,y2);
}
void query_y(int xx,int node,int l,int r,int y1)
{
if(tree[xx][node]==1)num++;
if(l+1==r)return ;
int mid=(l+r)>>1;
if(y1<mid)query_y(xx,node*2,l,mid,y1);
else query_y(xx,node*2+1,mid,r,y1);
}
void query_x(int node,int l,int r,int x1,int y1)
{
query_y(node,1,1,n+1,y1);
if(l+1==r)return ;
int mid=(l+r)>>1;
if(x1<mid)query_x(node*2,l,mid,x1,y1);
else query_x(node*2+1,mid,r,x1,y1);
}
int main()
{
int t,m,x1,x2,y1,y2;
char ch[10];
scanf("%d",&t);
while(t--)
{
memset(tree,0,sizeof(tree));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%s",ch+1);
if(ch[1]=='C')
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add_x(1,1,n+1,x1,x2+1,y1,y2+1);
}
else
{
num=0;
scanf("%d%d",&x1,&y1);
query_x(1,1,n+1,x1,y1);
printf("%d\n",num&1);
}
}
printf("\n");
}
return 0;
}
最新文章
- Wine——在Linux上运行Windows软件
- Zookeeper的学习材料
- 用AutoCompleteTextView实现历史记录提示
- 向数据库中全部表中增加一个字段的SQL
- php代码优化,mysql语句优化,面试需要用到的
- 新公司入职第一天遇到的 关于 CSS 单行溢出文本显示省略号...的问题
- asp.net pagebase获取缓存的方法
- 新手使用ThinkPHP3.2.3的命名空间问题
- 终于解决“Git Windows客户端保存用户名与密码”的问题
- 【超酷超实用】CSS3可滑动跳转的分页插件制作教程
- 【.net 深呼吸】项目中是否有必要删去多余的引用
- Android自定义底部带有动画的Dialog
- python 图像处理,画一个正弦函数
- SpringMVC国际化与文件上传
- [P1306] 斐波那契公约数 (矩阵快速幂+斐波那契数列)
- mysql 主从数据不一致 Slave_SQL_Running: No 解决方法
- jq以固定开头的class属性的名称
- rpm安装MySQL5.5后配置,在centos5上;mysql编译安装在centos6.5上;
- JDK1.7安装和环境配置
- Rime中州韵导入QQ五笔词库
热门文章
- url post 请求方法
- jsp中<;c:forEach varStatus=";status";>;的属性值问题
- js获取元素的页面坐标
- PG extract 函数示例
- UVA - 11082 Matrix Decompressing (最大流,技巧)
- iOS(iPhone,iPad))开发(Objective-C)开发库常用库索引
- 单源最短路Dijstra
- 快学UiAutomator配置编辑环境
- shell脚本,逻辑结构题练习。
- Java第十二次作业:什么是一维数组?什么是对象数组?吃金币游戏2.0版 新增炸弹功能 新增游戏倒计时功能 新增胜利失败检测功能 使用如鹏游戏引擎制作窗体 一维数组设置金币