1452: [JSOI2009]Count

Time Limit: 10 Sec  

Memory Limit: 64 MB

Submit: 2094  

Solved: 1232

[ ][ ][ ]

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

Source

[ ][ ][ ]

【题解】【树状数组】

【二维树状数组，不要想太多，只要把一维改成二维，给每种权值建一棵树状数组（权值数不超过100种），然后正常做就行】

#include
    
     #include
     
      #include
      
       using namespace std;int tree[310][310][110];int a[310][310],n,m,q;inline void add(int x,int y,int num,int val){	for (int i=x;i<=n;i+=i&(-i))	 for (int j=y;j<=m;j+=j&(-j))	  tree[i][j][num]+=val;}inline int ask(int x,int y,int num){	int sum=0;	for (int i=x;i>=1;i-=i&(-i))	 for (int j=y;j>=1;j-=j&(-j))	  sum+=tree[i][j][num];	return sum;}int main(){	int i,j;	scanf("%d%d",&n,&m);	for (i=1;i<=n;++i)	 for (j=1;j<=m;++j)	  {	  	scanf("%d",&a[i][j]);	  	add(i,j,a[i][j],1);	  }	scanf("%d",&q);	for (i=1;i<=q;++i)	 {	 	int num;	 	scanf("%d",&num);	 	if (num==1)	 	 {	 	 	int x,y,val;			scanf("%d%d%d",&x,&y,&val);			add(x,y,a[x][y],-1);			add(x,y,val,1);			a[x][y]=val;		  }		 else		  {		  	int x1,x2,y1,y2,val,ans;		  	scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&val);		  	int ans1=ask(x2,y2,val);		  	int ans2=ask(x1-1,y2,val);		  	int ans3=ask(x2,y1-1,val);		  	int ans4=ask(x1-1,y1-1,val);		  	ans=ans1-ans2-ans3+ans4;		  	printf("%d\n",ans);		  }	 }}