Count bzoj-1452 JSOI-2009
题目大意：请维护一个平面内的数据结构，支持：单点修改，查询矩形内给定权值出现次数。
注释：$1\le n,m\le 300$，$1\le Q \le 5000$，n和m分别是长和宽，Q是操作次数。
想法：显然，我们根据权值线段树，给这种数据结构起个名字... ...
二维权值树状数组。
我们对树状数组上的节点开一个桶，Tree[i][j][val]表示再以(i,j)右下端点、以(1,1)为左上端点的矩阵中权值为val的数的个数。
对于每个修改直接在对应权值上修改，查询向前查询即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tree[310][310][110],a[310][310],n,m;
inline int lowbit(int x){return x&(-x);}
void fix(int x,int y,int val,int flag)
{
for(int i=x;i<=(n);i+=lowbit(i))
{
for(int j=y;j<=(m);j+=lowbit(j))
{
tree[i][j][val]+=flag;
}
}
}
int query(int x,int y,int val)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ans+=tree[i][j][val];
}
}
return ans;
}
int main()
{
cin >> n >> m ;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
fix(i,j,a[i][j],1);
}
int q,opt,x1,x2,y1,y2,x,y,val; cin >> q ;
while(q--)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d%d",&x,&y,&val);
fix(x,y,a[x][y],-1);
a[x][y]=val;
fix(x,y,a[x][y],1);
}
else
{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&val);
printf("%d\n",query(x2,y2,val)+query(x1-1,y1-1,val)-query(x1-1,y2,val)-query(x2,y1-1,val));
}
}
return 0;
}
小结：树状数组是真tm好写... ...