【bzoj1452】[JSOI2009]Count 二维树状数组
2024-08-26 01:02:10
题目描述
输入
输出
样例输入
样例输出
1
2
题解
二维树状数组
一开始没看到 1≤c≤100 ,想到了主X树和X块,结果发现c的范围那么小。。。
二维树状数组水题,和一维的一样,向上修改,向下查询,把一个范围变为4个范围处理。
#include <cstdio>
int a[310][310] , f[110][310][310] , n , m;
void update(int p , int x , int y , int a)
{
int i , j;
for(i = x ; i <= n ; i += i & -i) for(j = y ; j <= m ; j += j & -j) f[p][i][j] += a;
}
int query(int p , int x , int y)
{
int i , j , ans = 0;
for(i = x ; i ; i -= i & -i) for(j = y ; j ; j -= j & -j) ans += f[p][i][j];
return ans;
}
int main()
{
int i , j , q , t , x1 , y1 , x2 , y2 , v;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= m ; j ++ ) scanf("%d" , &a[i][j]) , update(a[i][j] , i , j , 1);
scanf("%d" , &q);
while(q -- )
{
scanf("%d" , &t);
if(t == 1) scanf("%d%d%d" , &x1 , &y1 , &v) , update(a[x1][y1] , x1 , y1 , -1) , a[x1][y1] = v , update(a[x1][y1] , x1 , y1 , 1);
else scanf("%d%d%d%d%d" , &x1 , &x2 , &y1 , &y2 , &v) , printf("%d\n" , query(v , x2 , y2) - query(v , x2 , y1 - 1) - query(v , x1 - 1 , y2) + query(v , x1 - 1 , y1 - 1));
}
return 0;
}
最新文章
- Blender 之 Splash 代码分析
- OC笔记
- 错题726-java
- JAVA中线程池启动定时任务
- 三,samba
- iOS获取手机相关信息
- AVCaptureDevice的几个属性
- 两个字符串,若为数字则都相加,若有一个不为数字则,输出error
- Laravel框架——分页
- linux中fork创建进程讲解(转)
- 通过反射生成SQL的例子
- Nginx支持Socket转发过程详解
- Kotlin——最详细的接口使用、介绍
- python利用xlrd读取excel文件始终报错原因
- 【NLP】大白话讲解word2vec到底在做些什么
- 【Python全栈-HTML】HTML入门
- Benchmarking Zeebe: An Intro to How Zeebe Scales Horizontally and How We Measure It
- leetcode1008
- C#中DataSet、DataTable、DataReader的区别
- python之路----面向对象的封装特性