首页 > 代码库 > BZOJ 1452 JSOI 2009 Count 二维树状数组
BZOJ 1452 JSOI 2009 Count 二维树状数组
题目大意:有一个m*n的方格,每一个格子有他自己的权值。2种操作:
1.改变一个格子的权值。
2.查询所有的x1 <= x <= x2 && y1 <= y <= y2的中,有多少个格子颜色是c。
思路:好像是二维树状数组的样子,但是不知道怎么搞。后来研究了数据范围,发现格子最大300*300,颜色最多才100种,于是算一下300*300*100*4/1024/1024大概是35M,题目要求64M,可以搞了。(这里算的精确一点,我当时没怎么算,吧颜色开成300的了,结果100+M就MLE了。。)
维护100个二维树状数组,每一个代表一种颜色,然后根据容斥原理计算一个方块区间内的数量。更改的时候要改两次,第一次把之前的减去,然后加上改变之后的。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 310 using namespace std; int m,n; struct Complex{ int tree[MAX][MAX]; void Fix(int x,int y,int c) { for(int i = x;i <= m;i += i&-i) for(int j = y;j <= n;j += j&-j) tree[i][j] += c; } int GetSum(int x,int y) { int re = 0; for(int i = x;i;i -= i&-i) for(int j = y;j;j -= j&-j) re += tree[i][j]; return re; } }tree_arr[110]; int src[MAX][MAX]; int asks; int main() { cin >> m >> n; for(int i = 1;i <= m; ++i) for(int j = 1;j <= n; ++j) { scanf("%d",&src[i][j]); tree_arr[src[i][j]].Fix(i,j,1); } cin >> asks; for(int flag,i = 1;i <= asks; ++i) { scanf("%d",&flag); if(flag == 1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); tree_arr[src[x][y]].Fix(x,y,-1); src[x][y] = z; tree_arr[src[x][y]].Fix(x,y,1); } else { int x1,y1,x2,y2,c; scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c); int ans = tree_arr[c].GetSum(x2,y2); ans -= tree_arr[c].GetSum(x1 - 1,y2); ans -= tree_arr[c].GetSum(x2,y1 - 1); ans += tree_arr[c].GetSum(x1 - 1,y1 - 1); printf("%d\n",ans); } } return 0; }
BZOJ 1452 JSOI 2009 Count 二维树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。