Iahub does not like background stories, so he'll tell you exactly what this problem asks you for.
You are given a matrix a with n rows and n columns. Initially, all values of the matrix are zeros. Both rows and columns are 1-based, that is rows are numbered 1, 2, ..., n and columns are numbered 1, 2, ..., n. Let's denote an element on the i-th row and j-th column as ai, j.
We will call a submatrix (x0, y0, x1, y1) such elements ai, j for which two inequalities hold: x0 ≤ i ≤ x1, y0 ≤ j ≤ y1.
Write a program to perform two following operations:
- Query(x0, y0, x1, y1): print the xor sum of the elements of the submatrix (x0, y0, x1, y1).
- Update(x0, y0, x1, y1, v): each element from submatrix (x0, y0, x1, y1) gets xor-ed by value v.
The first line contains two integers: n (1 ≤ n ≤ 1000) and m (1 ≤ m ≤ 105). The number m represents the number of operations you need to perform. Each of the next m lines contains five or six integers, depending on operation type.
If the i-th operation from the input is a query, the first number from i-th line will be 1. It will be followed by four integers x0, y0, x1, y1. If thei-th operation is an update, the first number from the i-th line will be 2. It will be followed by five integers x0, y0, x1, y1, v.
It is guaranteed that for each update operation, the following inequality holds: 0 ≤ v < 262. It is guaranteed that for each operation, the following inequalities hold: 1 ≤ x0 ≤ x1 ≤ n, 1 ≤ y0 ≤ y1 ≤ n.
For each query operation, output on a new line the result.
3 5
2 1 1 2 2 1
2 1 3 2 3 2
2 3 1 3 3 3
1 2 2 3 3
1 2 2 3 2
3
2
After the first 3 operations, the matrix will look like this:
1 1 2
1 1 2
3 3 3
The fourth operation asks us to compute 1 xor 2 xor 3 xor 3 = 3.
The fifth operation asks us to compute 1 xor 3 = 2.
题意:
给你一个n×n的矩阵;初始时所有位置的值都为0;
m次操作:两种操作,一种是将某个矩形区域的值异或v,另一种是求一个矩形区域的异或和。
题解:
想办法维护(1,1)(x,y)的异或和,那么矩形区域的异或和就可以根据四个位置的异或和求出。由于异或操作比较特殊,在一个区域进行异或操作,那么这个区域的某个点的(1,1)(x,y)的异或和要么要异或上v,要么异或上0。这样,我们就可以利用二维树状数组,只进行单点更新就完成更新矩形区域的操作,另外,由于区域是否被更新跟奇偶性有关,因此跟据奇偶性来维护4种情况的树状数组。
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18+1LL;
const double Pi = acos(-1.0);
const int N = 1e3+, M = 1e5+, mod = 1e9+, inf = 2e9; int n,m,mp[N][N];
LL C[][N][N]; int get(int x,int y) {
int res = ;
if(x&) res += ;
if(y&) res += ;
return res;
}
LL ask(int x,int y) {
LL s = ;
int wh = get(x,y);
for(int i = x; i; i-= i & (-i))
for(int j = y; j; j -= j & (-j)) s^=C[wh][i][j];
return s;
}
void update(int x,int y,LL v) {
int wh = get(x,y);
for(int i = x; i < N; i+= i&(-i))
for(int j = y; j < N; j += j&(-j)) C[wh][i][j] ^= v;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = ; i <= m; ++i) {
int op,x1,x2,y1,y2;
LL v;
scanf("%d%d%d%d%d",&op,&x1,&y1,&x2,&y2);
if(op == ) {
LL a = ask(x2,y2);
LL b = , c = , d = ;
if(y1 > ) b = ask(x2,y1-);
if(x1 > ) c = ask(x1-,y2);
if(x1 > && y1 > ) d = ask(x1-,y1-);
printf("%I64d\n",a^b^d^c);
} else {
scanf("%I64d",&v);
update(x2+,y2+,v);
update(x2+,y1,v);
update(x1,y2+,v);
update(x1,y1,v);
}
}
return ;
}
Codeforces Round #198 (Div. 1) D. Iahub and Xors 二维树状数组*的更多相关文章
-
Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum (离线树状数组+前缀xor)
题目链接:http://codeforces.com/contest/703/problem/D 给你n个数,m次查询,每次查询问你l到r之间出现偶数次的数字xor和是多少. 我们可以先预处理前缀和X ...
-
Codeforces Round #510 (Div. 2) D. Petya and Array(离散化+反向树状数组)
http://codeforces.com/contest/1042/problem/D 题意 给一个数组n个元素,求有多少个连续的子序列的和<t (1<=n<=200000,abs ...
-
Codeforces Round #365 (Div. 2)-D Mishka and Interesting sum(树状数组)
题目链接:http://codeforces.com/contest/703/problem/D 思路:看了神犇的代码写的... 偶数个相同的数异或结果为0,所以区间ans[l , r]=区间[l , ...
-
Codeforces Round 261 Div.2 D Pashmak and Parmida&#39;s problem --树状数组
题意:给出数组A,定义f(l,r,x)为A[]的下标l到r之间,等于x的元素数.i和j符合f(1,i,a[i])>f(j,n,a[j]),求有多少对这样的(i,j). 解法:分别从左到右,由右到 ...
-
Codeforces Round #590 (Div. 3)【D题:26棵树状数组维护字符出现次数】
A题 题意:给你 n 个数 , 你需要改变这些数使得这 n 个数的值相等 , 并且要求改变后所有数的和需大于等于原来的所有数字的和 , 然后输出满足题意且改变后最小的数值. AC代码: #includ ...
-
VK Cup 2016 - Round 1 (Div. 2 Edition) B. Bear and Displayed Friends 树状数组
B. Bear and Displayed Friends 题目连接: http://www.codeforces.com/contest/658/problem/B Description Lima ...
-
Codeforces Round #371 (Div. 1) D. Animals and Puzzle 二维倍增
D. Animals and Puzzle 题目连接: http://codeforces.com/contest/713/problem/D Description Owl Sonya gave a ...
-
Codeforces 707 E. Garlands (二维树状数组)
题目链接:http://codeforces.com/problemset/problem/707/E 给你nxm的网格,有k条链,每条链上有len个节点,每个节点有一个值. 有q个操作,操作ask问 ...
-
Codeforces Round #198 (Div. 2) E. Iahub and Permutations —— 容斥原理
题目链接:http://codeforces.com/contest/340/problem/E E. Iahub and Permutations time limit per test 1 sec ...
随机推荐
-
javascript高级编程3第二章:在html中使用javascript
2.1 <script>元素 向html页面中插入javascript的主要方法,就是使用<script>元素.这个元素被加入到正式的html规范中.html4.01为< ...
-
ECMAScript 6十大特性
ES6入门 http://es6.ruanyifeng.com/ ES6排名前十的最佳特性列表 Default Parameters(默认参数) in ES6 Template Literals (模 ...
-
SQL Server 触发器2
触发器可以做很多事情,但也会带来很多问题.使用它的技巧在于在适当的时候使用,而不要在不适当的时候使用它们. 触发器的一些常见用途如下: 弹性参照完整性:实现很多DRI不能实现的操作(例如,跨数据库或服 ...
-
OpenCV探索之路(十一):轮廓查找和多边形包围轮廓
Canny一类的边缘检测算法可以根据像素之间的差异,检测出轮廓边界的像素,但它没有将轮廓作为一个整体.所以要将轮廓提起出来,就必须将这些边缘像素组装成轮廓. OpenCV中有一个很强大的函数,它可以从 ...
-
Qt开发陷阱一QSTACKWIDGET
原始日期:2015-10-14 00:55 1.使用QStackWidget控件的setCurrentIndex方法时,要注意参数0对应着ui上StackWidget的page1,而不是page0,没 ...
-
计蒜客NOIP模拟赛4 D2T1 鬼脚图
鬼脚图,又称画鬼脚,在日本称作阿弥陀签,是一种经典游戏,也是一种简易的决策方法,常常用来抽签或决定分配组合. 下图就是一张鬼脚图,其包含若干条竖线和若干条横线.请注意,横线只能水平连接相邻的两条竖线, ...
-
Python中多个列表与字典的合并方法
Python中多个列表与字典的合并方法 1多列表的合并 1)a+=b a=['] b = ['] a += b print(a) >>>['] 2) a.extend(b) a=[' ...
-
Perl正则表达式引用
正则表达式两篇: 基础正则 Perl正则 本文是对Perl正则的一点扩展,主要内容是使用qr//创建正则对象,以及一些其它的技巧. qr//创建正则对象 因为可以在正则模式中使用变量替换,所以我们可以 ...
-
HDU - 1542 扫描线入门+线段树离散化
扫描线算法+线段树维护简介: 像这种求面积的并集的题目,就适合用扫描线算法解决,具体来说就是这样 类似这种给出点的矩形的对角的点的坐标,然后求出所有矩形面积的交集的问题,可以采用扫描线算法解决.图如下 ...
-
Hive 表类型简述
Hive 表类型简述 表类型一.管理表或内部表Table Type: MANAGED_TABLE example: create table Inner(id int,name string, ...