POJ 2029

二维树状数组可解此题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) (x)&(-x)

using namespace std;
int sum[105][105],k,n,m;
int W,H;

void gp(int x,int y){
	int t;
	for(;x<=n;x+=lowbit(x))
	    for(t=y;t<=m;t+=lowbit(t))
	      sum[x][t]+=1;
}

int gs(int x,int y){
  int s=0,t;
  for(;x;x-=lowbit(x))
    for(t=y;t;t-=lowbit(t))
      s+=sum[x][t];
  return s;
}

int gst(int x1,int y1,int x2,int y2){
	return gs(x2,y2)-gs(x1-1,y2)-gs(x2,y1-1)+gs(x1-1,y1-1);
}

int main(){
	int s,h; int maxt;
	while(scanf("%d",&k),k){
		maxt=-1;
		memset(sum,0,sizeof(sum));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=k;i++){
			scanf("%d%d",&s,&h);
			gp(s,h);
		}
		scanf("%d%d",&W,&H);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				maxt=max(maxt,gst(i-W<=0?1:(i-W+1),j-H<=0?1:(j-H+1),i,j));
			}
		}
		printf("%d
",maxt);
	}
	return 0;
}