二维树状数组：类似于一维的状态下，二维存储的是一个区域内的状态。
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define N 105 5 #define lowbit(x) x&-x 6 using namespace std; 7 int f[N][N]; 8 void init() 9 { 10 memset(f,0,sizeof(f)); 11 } 12 int m,n; 13 void add(int x,int y,int v) 14 { 15 int i,j; 16 for(i=x;i<=n;i+=lowbit(i)) 17 for(j=y;j<=m;j+=lowbit(j)) 18 f[i][j]+=v; 19 } 20 int getsum(int x,int y) 21 { 22 int sum=0; 23 int i,j; 24 for(i=x;i>=1;i-=lowbit(i)) 25 for(j=y;j>=1;j-=lowbit(j)) 26 sum+=f[i][j]; 27 return sum; 28 } 29 int main() 30 { 31 int t; 32 int x,y; 33 int i,j,temp; 34 while(scanf("%d",&t)&&t) 35 { 36 scanf("%d%d",&n,&m); 37 init(); 38 for(i=0;i<t;i++) 39 { 40 scanf("%d%d",&x,&y); 41 add(x,y,1); 42 } 43 scanf("%d%d",&x,&y); 44 int max=0; 45 for(i=x;i<=n;i++) 46 for(j=y;j<=m;j++) 47 { 48 temp=getsum(i,j)-getsum(i,j-y)-getsum(i-x,j)+getsum(i-x,j-y); 49 max=max>temp?max:temp; 50 } 51 printf("%d\n",max); 52 } 53 return 0; 54 }