POJ 2155 Matrix (树状数组 && 区间计数)
2024-10-07 04:58:04
题意 : 给出一个N*N的矩阵, 矩阵只有可能包含0或1, 一开始则全部是0。对于矩阵可以进行两种操作, 第一种是输入 C x1 y1 x2 y2 表示, 对以(x1, y1)为左上角, 以(x2, y2)为右下角构成的矩形区域内的数全部进行取反操作, 即0变1、1变0。第二种是Q X Y, 表示查询现在这个矩阵的(X, Y)点到底是0还是1。总共有T次操作, 对于C操作进行相应的修改, 对于Q操作要对应输出!
分析 : 据说是楼教主出的题, 自己确实想不出什么高效的办法, 参考网上的题解, 才得知解题思想源自一篇国家队论文, 说简单一点就是对于题目要求的C操作, 实际上只要更新这个小矩形区域的四个点即可, 也就是不必全部照样更新。在Q操作查询时候也只要进行二维的树状数组进行(1,1)到(X, Y)点的矩形区域求和, 然后将求和结果%2, 如果得1即这个点被进行了奇数次操作, 所以应为1, 得0则反之。至于为什么或者如何做, 论文讲的很清楚, 请百度: 《浅谈信息学竞赛中的“0”和“1”》
瞎想 : 很值得借鉴的是对于是否是0或1的判断, 被转化成判断了对这个点操作次数的奇偶。还有对于区间的修改, 对于一维只进行两点的起始标记, 二维则进行四个点的起始标记, 这个也是厉害!
#include<stdio.h> #include<string.h> #define lowbit(i) (i&(-i)) ; int c[maxn][maxn], n; inline void add(int row, int col) { for(int i=row; i<=n; i+=lowbit(i)){ for(int j=col; j<=n; j+=lowbit(j)){ c[i][j]++; } } } int sum(int row, int col) { ; ; i-=lowbit(i)){ ; j-=lowbit(j)){ ans += c[i][j]; } } return ans; } inline void initialize(int k) { ; i<=k; i++){ memset(c[i], , sizeof(c[i])); } } int main(void) { int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%d", &n); initialize(n); int num; scanf("%d", &num); while(num--){ char command; scanf(" %c", &command); if(command=='C'){ int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); add(x1, y1); add(x2+, y1); add(x1, y2+); add(x2+, y2+); }else{ int x, y; scanf("%d%d", &x, &y); int SUM = sum(x, y); printf();//&1和%2好像效率一样! } } puts("");//注意这里, 用例之间要空个行, 避免PE } ; }
最新文章
- [USACO14OPEN] Dueling GPS&#39;s[最短路建模]
- Android Studio 修改字体
- linux mysql
- 【中途相遇法】【STL】BAPC2014 K Key to Knowledge (Codeforces GYM 100526)
- c++11 : Variadic Macros(变长参宏)
- Java Spring MVC
- 为 Devops 和系统管理员提供的 400+ 免费资源
- [每日一题] OCP1z0-047 :2013-07-22 group by 子句
- Struts2-2.了解struts.xml的查找顺序
- Flask 扩展 自定义扩展
- ACM 畅通工程
- 基于服务器AAA的实验
- 不需要再手写 onSaveInstanceState 了,因为你的时间非常值钱
- OceanBase 2.0让百万支付不是梦?
- SpringCloud注册中心环境搭建euraka
- [Python]查询oracle导出结果至Excel并发送邮件
- Oracle数据库修改LISTENER的监听端口
- Java之.jdk安装-Linux
- OpenGL ES 3.0之Uniform详解
- New Game! (最短路+建图)