二维树状数组裸题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
// <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; } |
说点什么