BZOJ 1452: [JSOI2009]Count [二维树状数组]-白红宇

BZOJ 1452: [JSOI2009]Count [二维树状数组]

阅读量：5046 次

发布时间：2019-06-12

本文共 1481 字，大约阅读时间需要 4 分钟。

题意：修改一个位置的颜色，询问子矩阵某种颜色的数量，颜色$\le\ 100$

$fuck$我个沙茶连树状数组都不会写了，没用$lowbit()$没用$i,j$

每种颜色开一个二维树状数组....

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N=301,M=101;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,m,c[M][N][N],col[N][N];int Q,op,x,y,x1,y1,x2,y2,v;inline int lowbit(int x){
   return x&-x;}inline void add(int c[N][N],int x,int y,int v){    for(int i=x;i<=n;i+=lowbit(i))        for(int j=y;j<=m;j+=lowbit(j)) c[i][j]+=v;}inline int sum(int c[N][N],int x,int y){    int re=0;    for(int i=x;i;i-=lowbit(i))        for(int j=y;j;j-=lowbit(j)) re+=c[i][j];    return re;}int main(){    freopen("in","r",stdin);    n=read();m=read();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            col[i][j]=read();            add(c[col[i][j]],i,j,1);        }    Q=read();    while(Q--){        op=read();        if(op==1){            x=read();y=read();v=read();            add(c[col[x][y]],x,y,-1);            col[x][y]=v;            add(c[col[x][y]],x,y,1);        }else{            x1=read()-1;x2=read();y1=read()-1;y2=read();v=read();            int ans=sum(c[v],x2,y2)-sum(c[v],x1,y2)-sum(c[v],x2,y1)+sum(c[v],x1,y1);            printf("%d\n",ans);        }    }}