【BZOJ1452】【JSOI2009】Count

二维树状数组裸题

// <1452.cpp> - 07/25/16 16:40:37
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=310;
const int INF=1e9;
#define lowbit(x) x&-x
int n,m,cl[MAXN][MAXN],c[110][MAXN][MAXN];
inline void add(int k,int x,int y,int z){
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))c[k][i][j]+=z;
}
inline int get(int k,int x,int y){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))res+=c[k][i][j];
    return res;
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)add(cl[i][j]=gi(),i,j,1);
    int q=gi();
    while(q--){
        int tp=gi();
        if(tp==1){
            int x=gi(),y=gi();
            add(cl[x][y],x,y,-1);
            add(cl[x][y]=gi(),x,y,1);
        }else{
            int x1=gi()-1,x2=gi(),y1=gi()-1,y2=gi(),c=gi();
            printf("%d\n",get(c,x2,y2)+get(c,x1,y1)-get(c,x2,y1)-get(c,x1,y2));
        }
    }
    return 0;
}

// <1452.cpp> - 07/25/16 16:40:37

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

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

if(ch=='-')fh=-1,ch=getchar();

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

return fh*res;

}

const int MAXN=310;

const int INF=1e9;

#define lowbit(x) x&-x

int n,m,cl[MAXN][MAXN],c[110][MAXN][MAXN];

inline void add(int k,int x,int y,int z){

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

for(int j=y;j<=m;j+=lowbit(j))c[k][i][j]+=z;

}

inline int get(int k,int x,int y){

int res=0;

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

for(int j=y;j;j-=lowbit(j))res+=c[k][i][j];

return res;

}

int main(){

n=gi(),m=gi();

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

for(int j=1;j<=m;j++)add(cl[i][j]=gi(),i,j,1);

int q=gi();

while(q--){

int tp=gi();

if(tp==1){

int x=gi(),y=gi();

add(cl[x][y],x,y,-1);

add(cl[x][y]=gi(),x,y,1);

}else{

int x1=gi()-1,x2=gi(),y1=gi()-1,y2=gi(),c=gi();

printf("%d\n",get(c,x2,y2)+get(c,x1,y1)-get(c,x2,y1)-get(c,x1,y2));

}

return 0;

}