BZOJ1452 [JSOI2009]Count

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

正解：二维树状数组

解题报告：

　　这是一道送肉题。二维树状数组直接维护每种颜色的出现次数，颜色编号也很小，所以直接开数组存就可以了。

 1 //It is made by jump~
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 #ifdef WIN32   
14 #define OT "%I64d"
15 #else
16 #define OT "%lld"
17 #endif
18 using namespace std;
19 typedef long long LL;
20 const int MAXC = 150;
21 const int MAXN = 311;
22 int n,m,ans;
23 int shu[MAXC][MAXN][MAXN];
24 int a[MAXN][MAXN];
25 int que[2][2];
26 
27 inline int getint()
28 {
29        int w=0,q=0;
30        char c=getchar();
31        while((c<'0' || c>'9') && c!='-') c=getchar();
32        if (c=='-')  q=1, c=getchar();
33        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
34        return q ? -w : w;
35 }
36 
37 inline void add(int x,int y,int val,int hh){
38     for(int i=x;i<=n;i+=i&(-i))
39     for(int j=y;j<=m;j+=j&(-j))
40         shu[val][i][j]+=hh;
41 }
42 
43 inline int ask(int x,int y,int val){
44     int tot=0;
45     for(int i=x;i;i-=i&(-i))
46     for(int j=y;j;j-=j&(-j))
47         tot+=shu[val][i][j];
48     return tot;
49 }
50 
51 inline void query(int val){
52     ans=ask(que[1][0],que[1][1],val)-ask(que[0][0]-1,que[1][1],val)-ask(que[1][0],que[0][1]-1,val)+ask(que[0][0]-1,que[0][1]-1,val);
53 }
54 
55 inline void work(){
56     n=getint(); m=getint(); 
57     for(int i=1;i<=n;i++)
58     for(int j=1;j<=m;j++)
59         a[i][j]=getint(),add(i,j,a[i][j],1);
60     int q=getint();
61     int ljh; int x,y,z;
62     while(q--) {
63     ljh=getint();
64     if(ljh==1) {
65         x=getint(); y=getint(); z=getint();
66         add(x,y,a[x][y],-1);
67         add(x,y,z,1); a[x][y]=z;
68     }
69     else{
70         que[0][0]=getint();  que[1][0]=getint();
71         que[0][1]=getint();  que[1][1]=getint();
72         z=getint();
73         query(z); printf("%d
",ans);
74     }
75     }
76 }
77 
78 int main()
79 {
80   work();
81   return 0;
82 }