题解 P4054 【[JSOI2009]计数问题】
sukimo
2020-06-26 17:18:16
可以说是二维$BIT$单点修改区间查询的板子题。原理和一维$BIT$类似。考虑到数据规模不大，可以对于每一个权值开一个$BIT$，然后修改时对于原权值的$BIT$对应位置$--$，新权值的$BIT$对应位置$++$。
代码：
```
#include<bits/stdc++.h>
#define MXq 200005
using namespace std;
int n,m,mat[305][305],ans[MXq],tree[105][305][305];
int lowbit(int x){return x&-x;}
void add(int type,int x,int y,int v){
while(x<=n){
int _y=y;while(_y<=m){tree[type][x][_y]+=v;_y+=lowbit(_y);}x+=lowbit(x);
}
}
int pref(int type,int x,int y){
int tot=0;
while(x>=1){
int _y=y;while(_y>=1){tot+=tree[type][x][_y];_y-=lowbit(_y);}x-=lowbit(x);
}
return tot;
}
int query(int type,int x1,int y1,int x2,int y2){
return pref(type,x2,y2)+pref(type,x1-1,y1-1)-pref(type,x1-1,y2)-pref(type,x2,y1-1);
}
int main(){
int q,_top=0;cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{cin>>mat[i][j];add(mat[i][j],i,j,1);}
cin>>q;
for(int i=1;i<=q;i++){
int _q;cin>>_q;
if(_q==1){
int x,y,c;cin>>x>>y>>c;add(mat[x][y],x,y,-1);add(c,x,y,1);mat[x][y]=c;
}
else{
int x1,y1,x2,y2,c;cin>>x1>>x2>>y1>>y2>>c;
ans[++_top]=query(c,x1,y1,x2,y2);
}
}
for(int i=1;i<=_top;i++)cout<<ans[i]<<endl;
return 0;
}
```