bzoj1452 [JSOI2009]Count ——二维树状数组

中文题面,给你一个矩阵,每一个格子有数字,有两种操作。

1. 把i行j列的值更改

2. 询问两个角坐标分别为(x1,y1) (x2,y2)的矩形内有几个值为z的点。

这一题的特点就是给出的z的数据范围很小,只有1~100,所以我们可以开100个300X300的二维树状数组来解决问题。

#include<bits/stdc++.h>
using namespace std;
int a[][][];
int s[][];
int n,m,k;
int lowbit(int x)
{
return x&-x;
}
int add(int x,int y,int z,int w)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j)) a[i][j][z]+=w;
}
int find(int x,int y,int z)
{
int ans=;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
{
ans+=a[i][j][z];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&s[i][j]);
add(i,j,s[i][j],);
}
scanf("%d",&k);
int ddd,x,y,z,xx,yy;
for(int i=;i<k;i++)
{
scanf("%d",&ddd);
if(ddd==)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,s[x][y],-);
add(x,y,z,);
s[x][y]=z;
}
else
{
scanf("%d%d%d%d%d",&x,&xx,&y,&yy,&z);
int ans=find(xx,yy,z)-find(xx,y-,z)-find(x-,yy,z)+find(x-,y-,z);
//cout<<find(xx,yy,z)<<find(xx,y-1,z)<<find(x-1,yy,z)<<find(x-1,y-1,z)<<endl;
printf("%d\n",ans);
}
}
}
上一篇:Note: CHAPTER 2 Data Models and Query Languages


下一篇:Chapter Two