//POJ 2029 Get Many Persimmon Trees 二维线段树 单点更新 区间求和
/*
题意:一个0,1矩阵,在其n*m的子矩阵中找出含有1最多的,输出最多的数量
思路:二维线段树
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 105
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int n,m,k;
int sum[N<<2][N<<2];
void SubUpdate(int rt,int l,int r,int y,int t){
if(l == r)
++sum[t][rt];
else{
int mid = (l + r) >> 1;
if(y <= mid) SubUpdate(lson,y,t);
else SubUpdate(rson,y,t);
sum[t][rt] = sum[t][rt<<1] + sum[t][rt<<1|1];
}
}
void Update(int rt,int l,int r,int x,int y){
SubUpdate(1,1,m,y,rt);
if(l!=r){
int mid = (l + r) >> 1;
if(x <= mid) Update(lson,x,y);
else Update(rson,x,y);
}
}
int SubQuery(int rt,int l,int r,int LY,int RY,int t){
if(LY <= l && RY >= r)
return sum[t][rt];
int mid = (l + r) >> 1;
int ans = 0;
if(LY <= mid) ans += SubQuery(lson,LY,RY,t);
if(RY > mid ) ans += SubQuery(rson,LY,RY,t);
return ans;
}
int Query(int rt,int l,int r,int LX,int RX,int LY,int RY){
if(LX <= l && RX >= r)
return SubQuery(1,1,m,LY,RY,rt);
int mid = (l + r) >> 1;
int ans = 0;
if(LX <= mid) ans += Query(lson,LX,RX,LY,RY);
if(RX > mid ) ans += Query(rson,LX,RX,LY,RY);
return ans;
}
int Max(int x,int y){
return x>y?x:y;
}
int main(){
int i,j;
int a,b;
while(scanf("%d",&k),k){
scanf("%d %d",&n,&m);
memset(sum,0,sizeof(sum));
while(k--){
scanf("%d %d",&a,&b);
Update(1,1,n,a,b);
}
scanf("%d %d",&a,&b);
int mmax= 0;
for(i = 1; i+a-1 <= n; ++i)
for(j = 1; j+b-1 <= m; ++j)
mmax = Max(mmax,Query(1,1,n,i,i+a-1,j,j+b-1));
printf("%d\n",mmax);
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1747400
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1740501
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ2002-Squares 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告