//POJ 2155 Matrix 二维线段树 奇妙的成段更新 单点查询
/*
题意:
有一个n*n的矩阵,初始化全部为0。有2中操作;
1、给一个子矩阵,将这个子矩阵里面所有的0变成1,1变成0
2、询问某点的值
思路:
二维线段树,一维线段树的成段更新需要lazy。
引申到二维线段树应该需要一个lazy,一个sublazy,可是这里什么都不用。
奇妙之处在于这题的操作是异或,当某一段区间需要异或操作时候,
不必更新到它所有的叶子结点,可以像lazy那样父结点异或后就返回
只要在查询时从根节点开始异或,而不是直接查叶子结点,这样相当于将lazy储存在父结点上
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int sum[N<<2][N<<2];
int n,m,ans;
void SubBuild(int rt,int l,int r,int t){
sum[t][rt] = 0;
if(l!=r){
int mid = (l + r) >> 1;
SubBuild(lson,t);
SubBuild(rson,t);
}
}
void Build(int rt,int l,int r){
SubBuild(1,1,n,rt);
if(l != r){
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
}
}
void SubUpdate(int rt,int l,int r,int LY,int RY,int t){
if(LY <= l && RY >= r)
sum[t][rt] ^= 1;
else{
int mid = (l + r) >> 1;
if(LY <= mid) SubUpdate(lson,LY,RY,t);
if(RY > mid) SubUpdate(rson,LY,RY,t);
}
}
void Update(int rt,int l,int r,int LX,int RX,int LY,int RY){
if(LX <= l && RX >= r)
SubUpdate(1,1,n,LY,RY,rt);
else{
int mid = (l + r) >> 1;
if(LX <= mid) Update(lson,LX,RX,LY,RY);
if(RX > mid) Update(rson,LX,RX,LY,RY);
}
}
void SubQuery(int rt,int l,int r,int y,int t){
ans ^= sum[t][rt];//这里是异或!!!
if(l!=r){
int mid = (l + r) >> 1;
if(y <= mid) SubQuery(lson,y,t);
else SubQuery(rson,y,t);
}
}
void Query(int rt,int l,int r,int x,int y){
SubQuery(1,1,n,y,rt);
if(l!=r){
int mid = (l + r) >> 1;
if(x <= mid) Query(lson,x,y);
else Query(rson,x,y);
}
}
int main(){
int T,ca = 1;
char op[5];
int a,b,c,d;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
Build(1,1,n);
if(ca++ != 1)
puts("");
while(m--){
scanf("%s",op);
if(op[0] == 'C'){
scanf("%d %d %d %d",&a,&b,&c,&d);
Update(1,1,n,a,c,b,d);
}
else{
scanf("%d %d",&a,&b);
ans = 0;
Query(1,1,n,a,b);
printf("%d\n",ans);
}
}
}
return 0;
}
分享到:
相关推荐
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
POJ题解 个人写法 线段树每个人都不一样
poj 2763 程序 线段树 LCA 2000MS AC
线段树、树状数组算法入门 加 poj解题报告 pdf文档
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同...poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
NULL 博文链接:https://128kj.iteye.com/blog/1747400
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ2002-Squares 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告