BZOJ 1452 Count（二维树状数组）

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1452

题意：给出一个数字矩阵（矩阵中任何时候的数字均为[1,100]），两种操作：（1）修改某个位置的数字；（2）求某个子矩阵中某个数字的个数。

思路：二维树状数组的操作看起来跟一维的差不多，只是循环改为两重而已。主要操作有：（1）增加某个位置的值；（2）询问[1,1,x,y]子矩阵的和。利用（2）操作以及区间的减法操作我们能求出任意一个子矩阵的数字和。这道题用a[i][x][y]来记录关于数字i的信息。

int a[105][N][N];

void add(int a[N][N],int x,int y,int t)
{
int i,j;
for(i=x;i<N;i+=i&-i) for(j=y;j<N;j+=j&-j)
{
a[i][j]+=t;
}
}

int query(int a[N][N],int x,int y)
{
int ans=0,i,j;
for(i=x;i;i-=i&-i) for(j=y;j;j-=j&-j)
{
ans+=a[i][j];
}
return ans;
}

int query(int a[N][N],int x1,int y1,int x2,int y2)
{
return query(a,x2,y2)-query(a,x1-1,y2)-query(a,x2,y1-1)+query(a,x1-1,y1-1);
}

int n,m;
int b[N][N];

int main()
{
Rush(n)
{
RD(m); clr(a,0);
int i,j,x;
FOR1(i,n) FOR1(j,m)
{
RD(x);
add(a[x],i,j,1);
b[i][j]=x;
}
int Q;
RD(Q);
int op,x1,x2,y1,y2,c;
while(Q--)
{
RD(op);
if(op==1)
{
RD(x1,y1,c);
add(a[b[x1][y1]],x1,y1,-1);
b[x1][y1]=c;
add(a[c],x1,y1,1);
}
else
{
RD(x1,x2); RD(y1,y2); RD(c);
PR(query(a[c],x1,y1,x2,y2));
}
}
}
}

巴特西

BZOJ 1452 Count（二维树状数组）

最新文章

热门文章