[bzoj1452] [JSOI2009]Count
5854 ワード
FallDreamのブログから、許可なく転載しないでください.ありがとうございます.
n*mの行列があり、各点に重み値があります.
2つの操作をサポートする必要があります:1)1つの点の重み値を変更する2)矩形内の重み値がcの個数をクエリーする
n,m<=300 q<=20000重み<=100
権値は少し小さいでしょう.では、それぞれの重み値に2 Dツリー配列を開きましょう.
転載先:https://www.cnblogs.com/FallDream/p/bzoj2452.html
n*mの行列があり、各点に重み値があります.
2つの操作をサポートする必要があります:1)1つの点の重み値を変更する2)矩形内の重み値がcの個数をクエリーする
n,m<=300 q<=20000重み<=100
権値は少し小さいでしょう.では、それぞれの重み値に2 Dツリー配列を開きましょう.
#include
#include
#define MN 300
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int s[105][MN+5][MN+5],c[MN+5][MN+5],n,m;
void renew(int c,int x,int y,int ad)
{
for(int i=x;i<=n;i+=i&(-i))
for(int j=y;j<=m;j+=j&(-j))
s[c][i][j]+=ad;
}
int query(int c,int x,int y)
{
int sum=0;
for(int i=x;i;i-=i&(-i))
for(int j=y;j;j-=j&(-j))
sum+=s[c][i][j];
return sum;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
c[i][j]=read(),renew(c[i][j],i,j,1);
for(int q=read();q--;)
{
int op=read();
if(op==1)
{
int x=read(),y=read(),col=read();
renew(c[x][y],x,y,-1);renew(col,x,y,1);
c[x][y]=col;
}
else
{
int x=read(),x2=read(),y=read(),y2=read(),c=read();
printf("%d
",query(c,x2,y2)+query(c,x-1,y-1)-query(c,x-1,y2)-query(c,x2,y-1));
}
}
return 0;
}
転載先:https://www.cnblogs.com/FallDream/p/bzoj2452.html