【BZOJ1452】[JSOI2009]Count（树状数组）

题面

BZOJ

洛谷

题解

数据范围这么小？不是对于每个颜色开一个什么东西记一下就好了吗。

然而我不会二维树状数组？

不存在的，凭借多年树套树经验自己\(yy\)一下就好了。

一维是后缀加法，二维当然就是给整个矩阵加法了啊。

#include<iostream>

#include<cstdio>

using namespace std;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,Q,a[303][303];

int c[103][303][303];

int lb(int x){return x&(-x);}

void modify(int p,int x,int y,int w)

{

	for(int i=x;i<=n;i+=lb(i))

		for(int j=y;j<=m;j+=lb(j))

			c[p][i][j]+=w;

}

int Query(int p,int x,int y)

{

	int ret=0;

	for(int i=x;i;i-=lb(i))

		for(int j=y;j;j-=lb(j))

			ret+=c[p][i][j];

	return ret;

}

int Query(int p,int x1,int y1,int x2,int y2)

{

	return Query(p,x2,y2)-Query(p,x2,y1-1)-Query(p,x1-1,y2)+Query(p,x1-1,y1-1);

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			modify(a[i][j]=read(),i,j,1);

	Q=read();

	while(Q--)

	{

		int opt=read();

		if(opt==1)

		{

			int x=read(),y=read(),w=read();

			modify(a[x][y],x,y,-1);

			modify(a[x][y]=w,x,y,1);

		}

		else

		{

			int x1=read(),x2=read(),y1=read(),y2=read(),w=read();

			printf("%d\n",Query(w,x1,y1,x2,y2));

		}

	}

	return 0;

}