[bzoj1452][树状数组]Count

本文主要是介绍[bzoj1452][树状数组]Count，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

3 3
1 2 3
3 2 1
2 1 3
3
2 1 2 1 2 1
1 2 3 2
2 2 3 2 3 2

Sample Output

1
2

题解

二维树状数组
s[p][i][j]表示，以（1,1）为左上端点到（i,j）为右下端点的矩阵，共有多少个颜色p
然后按照一维数组转移就好了
有个小错误要提示一下，不能把矩阵展开来做，就是不能s[p][i]
因为这样的话要多一个for去枚举每一行，直接TLE。。因为这个挂了一会

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int s[110][310][310];
int map[310][310];
int n,m;
int lowbit(int x){return x&-x;}
void change(int p,int x,int y,int k)
{for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))s[p][i][j]+=k;
}
int findsum(int p,int x,int y)
{int ans=0;for(int i=x;i>=1;i-=lowbit(i))for(int j=y;j>=1;j-=lowbit(j))ans+=s[p][i][j];return ans; 
}
int q;
int main()
{memset(s,0,sizeof(s));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&map[i][j]);change(map[i][j],i,j,1);}}scanf("%d",&q);while(q--){int op;scanf("%d",&op);if(op==1){int x,y,c;scanf("%d%d%d",&x,&y,&c);change(map[x][y],x,y,-1);map[x][y]=c;change(map[x][y],x,y,1);}else{int x1,x2,y1,y2,c;scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);int ans=0;ans+=findsum(c,x2,y2);ans-=findsum(c,x1-1,y2);ans-=findsum(c,x2,y1-1);ans+=findsum(c,x1-1,y1-1);printf("%d\n",ans);}}return 0;
}

这篇关于[bzoj1452][树状数组]Count的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---