题目描述
一个n*m的方格，初始时每个格子有一个整数权值。接下来每次有2种操作：
改变一个格子的权值；
- 求一个子矩阵中某种特定权值出现的个数。
输入输出格式
输入格式：
第一行有两个数N,M。
接下来N行，每行M个数，第i+1行第j个数表示格子(i,j)的初始权值。
接下来输入一个整数Q。
之后Q行，每行描述一个操作。
操作1：“1 x y c”(不含双引号)。表示将格子(x,y)的权值改成c（1<=x<=n,1<=y<=m,1<=c<=100)。
操作2：“2 x1 x2 y1 y2 c”(不含双引号，x1<=x2,y1<=y2)。表示询问所有满足格子颜色为c，且x1<=x<=x2,y1<=y<=y2的格子(x,y)的个数。
输出格式：
对于每个操作2，按照在输入中出现的顺序，依次输出一行一个整数表示所求得的个数。
输入输出样例
输入样例#1：
3 31 2 33 2 12 1 332 1 2 1 2 11 2 3 22 2 3 2 3 2
输出样例#1：
12
说明
数据规模：30%的数据，满足：n,m<=30,Q<=50000
?????100%的数据，满足：n,m<=300,Q<=200000
解题思路：
一看是二维树状数组，自己A，
漏点：没看清数据范围，还是没认真读题，废物。
也算是进步吧。
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int n,m,Q,a[400][400];int t[330][330][120];void add(int x,int y,int k,int d){ ???for(int i=x;i<=n;i+=(i&(-i))) ????for(int j=y;j<=m;j+=(j&(-j))) ?????t[i][j][k]+=d;}int ask(int x,int y,int c){ ???int ans=0; ???for(int i=x;i;i-=(i&(-i))) ????for(int j=y;j;j-=(j&(-j))) ?????ans+=t[i][j][c]; ???return ans;}int query(int x1,int y1,int x2,int y2,int c){ ???return ask(x2,y2,c)-ask(x1-1,y2,c)-ask(x2,y1-1,c)+ask(x1-1,y1-1,c);}int main(){ ???scanf("%d%d",&n,&m); ???for(int i=1;i<=n;++i) ????for(int j=1;j<=n;++j) ????{ ????????scanf("%d",&a[i][j]); ????????add(i,j,a[i][j],1); ????} ???scanf("%d",&Q); ???while(Q--) ???{ ???????int op,x1,y1,x2,y2,c;scanf("%d",&op); ???????if(op==1) ???????{ ???????????scanf("%d%d%d",&x1,&y1,&c); ???????????add(x1,y1,a[x1][y1],-1); ???????????a[x1][y1]=c; ???????????add(x1,y1,c,1); ???????}else{ ???????????scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c); ???????????printf("%d\n",query(x1,y1,x2,y2,c)); ???????} ???} ???return 0;}我坚信我的前方是光明一片。
[JSOI2009]计数问题
原文地址：https://www.cnblogs.com/adelalove/p/8457375.html