又是一道树状数组的题目,而且是一道二维的好题
题目要求是,一些操作,可能是对某个矩阵内的所有值取反,可能是问的是某个位置的值
如图
假如我们要把B矩阵的所有值都取反,我们只需要操纵矩阵的四个顶点即可,更新左下角顶点的值增1相当于把区域ABCD的变换次数增1,左上角顶点的值增1,相当于区域AC的变换次数增1,右上角顶点的值增1,相当于区域C的变换次数增1,右下角顶点的值增1,相当于区域CD的变换次数增1,最后我们可以发现,除了B区域外,A,C,D,都增加了偶数次的变换,相当于没有变化。所以,每次我们只需对四个顶点进行增1操作即可。在这里,我们应用了树状数组的一个性质,就是如果一个靠前的数据发生了变化,那么和其相关的求和问题都发生了变化。
那么问题问的是某个位置的值,比如(x,y),那么在(1,1)(x,y)这个矩阵中,如果有一些数进行过增1操作,那么必然(x,y)点的值也做了相应的变换。那么问题就转化为了求这个矩阵内所有值的和,然后判断其奇偶性。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 1005
#define INF 1000000000
#define eps 1e-7
using namespace std;
int a[MAXN][MAXN], n;
char s[5];
int lowbit(int x)
{
return x & -x;
}
void modify(int x, int y, int val)
{
for(int i = x; i <= n; i += lowbit(i))
for(int j = y; j <= n; j += lowbit(j))
a[i][j] += val;
}
int get_sum(int x, int y)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
sum += a[i][j];
return sum;
}
int main()
{
int T, m, x1, y1, x2, y2;
scanf("%d", &T);
while(T--)
{
memset(a, 0, sizeof(a));
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%s", s);
if(s[0] == 'C')
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
modify(x1, y1, 1);
modify(x2 + 1, y2 + 1, 1);
modify(x1, y2 + 1, 1);
modify(x2 + 1, y1, 1);
}
else if(s[0] == 'Q')
{
scanf("%d%d", &x1, &y1);
printf("%d\n", get_sum(x1, y1) % 2);
}
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1744222
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1745671
晒代码之二——多重背包(POJ1276)
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
西工大POJ习题第五季,数组这类的代码,有截图
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1757060
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
树状数组解决区间操作_高效 对数组的某个区间进行两种操作:1)求和 2)每个数据加常数。要求:时间复杂度低
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告