【bzoj1452】[JSOI2009]Count 二维树状数组

题目描述

输入

输出

样例输入

样例输出

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;

}