1452: [JSOI2009]Count

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 3135 Solved: 1828
[Submit][Status][Discuss]

Description

一个N*M的方格，初始时每个格子有一个整数权值，接下来每次有2个操作:

改变一个格子的权值

求一个子矩阵中某个特定权值出现的个数

Input

每一行有两个数字N，M

接下来N行，每行M个数字。第i+1行第j个数字表示格子(i,j)的初值

接下来输入一个Q，后面Q行每行描述一个操作

操作1:

1 x y c，表示将格子(x,y)的值变为c

操作2:

2 x1 x2 y1 y2 c，表示询问所有满足格子中数字为c的格子数字

(n,m<=300,Q<=5000)

(1<=x<=N,1<=y<=M,1<=c<=100)

(x1<=x<=x2,y1<=y<=y2)

Output

对于每个操作2,按输入中出现的顺序，依次输出一行一个整数表示所求得的个数

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

逛了一天的漫展，好累Orz

重新学习一下树状数组（我什么时候学过来着

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int n,m,q;
 7 int mp[305][305];
 8 int t[105][305][305];
 9 
10 int lowbit(int x){return x&(-x);}
11 void update(int x,int y,int c,int v)
12 {
13     for(int i=x;i<=n;i+=lowbit(i))
14         for(int j=y;j<=m;j+=lowbit(j))
15             t[c][i][j]+=v;
16 }
17 
18 int ask(int x,int y,int c)
19 {
20     int tmp=0;
21     for(int i=x;i;i-=lowbit(i))
22         for(int j=y;j;j-=lowbit(j))
23             tmp+=t[c][i][j];
24     return tmp;
25 }
26 
27 int main()
28 {
29     scanf("%d%d",&n,&m);
30     for(int i=1;i<=n;i++)
31         for(int j=1;j<=m;j++)
32         {
33             scanf("%d",&mp[i][j]);
34             update(i,j,mp[i][j],1);
35         }
36     scanf("%d",&q);
37     while(q--)
38     {
39         int f;
40         scanf("%d",&f);
41         int x1,y1,x2,y2,c;
42         if(f==1)
43         {
44             scanf("%d%d%d",&x1,&y1,&c);
45             update(x1,y1,mp[x1][y1],-1);
46             mp[x1][y1]=c;
47             update(x1,y1,mp[x1][y1],1);
48         }
49         else
50         {
51             scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
52             int ans=ask(x1-1,y1-1,c)+ask(x2,y2,c)-ask(x1-1,y2,c)-ask(x2,y1-1,c);
53             printf("%d
",ans);
54         }
55     }
56     return 0;
57 }