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
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
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 ????????else50 ????????{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\n",ans);54 ????????}55 ????}56 ????return 0;57 }1452: [JSOI2009]Count
原文地址：https://www.cnblogs.com/InWILL/p/9740741.html