首页 > 代码库 > [bzoj1452] [JSOI2009]Count

[bzoj1452] [JSOI2009]Count

2024-09-14 03:53:40   214人阅读

来自FallDream的博客，未经允许，请勿转载，谢谢。

 

有一个n*m的矩阵，每个点有一个权值。

需要支持两种操作：1)改变一个点的权值2)查询一个矩形内权值为c的个数

n,m<=300 q<=200000 权值<=100

权值有点小吧？那就每种权值开一个二维树状数组呗

#include<cstdio>#include<iostream>#define MN 300using 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\n",query(c,x2,y2)+query(c,x-1,y-1)-query(c,x-1,y2)-query(c,x2,y-1));        }    }    return 0;}

 

[bzoj1452] [JSOI2009]Count


联系
我们