发现坐标的范围很大,而点并不是很多,首先想到了离散化的方法。然后横向扫描每个带状的区间,对于每个带状区间,再纵向扫描其中点的个数。这种方法是最容易想到的,但是时间复杂度却高达O(N^2logN)。关键在于优化每次确定带状区间的纵向扫描。
显然对于确定的带状区间,我们扫描时只需考虑它们的纵坐标。如果我们把一个纵坐标为y的点描述成两个事件(y,1)和 (y+h+1,-1),然后把所有事件按照第一关键字排序,定义S[i]为前i项事件的第二关键字之和,那么Max{S[i]}就是确定的带状区间内高度 为w的矩形最多覆盖到的点数。为什么是这样,我们可以想象有两个挡板,分别是y=A-h-1(下板)和y=A(上板),从下向上移动挡板,从而确定一个矩 形。某个点的第一个事件为(y,1),当上板A=y时,该点被覆盖,若A继续增大,使得A-h-1=y,该点就恰好离开了覆盖区域,反过来我们可以以为是 A=y+h+1,所以定义第二个事件为(y+h+1,-1)。这样,前i个事件的第二关键字和S[i],就代表了矩形在某个位置时覆盖的点数。S[i]的 最大值就是确定的带状区间内最大的覆盖点数。
带状区间的左右扫描,也可以考虑成两个挡板之间的问题,首先确定挡板的初始位置在最左端,依次向右移动左右两个挡板。确定一个区间后,统 计点事件的最大前缀和成了最关键的问题。由于左右挡板是移动的,我们需要动态统计一个排序结构。于是我们想到了用平衡树,维护每个点事件的第一关键字(y 坐标)升序,并记录权。移动右挡板时,把右挡边新位置所在线上的所有点对应的两个点事件加入平衡树;移动左挡板时,把左挡板时,把左挡边所在线上的所有点 事件从平衡树中删除。
为了快速统计出最大的前缀和,在此基础上,我们还需要对于平衡树中每个节点维护其子树所有节点权值和,以及子树中最大的前缀和。定义p的权值为p.w,以节点p为根的子树的权值和为p.s,以节点p为根的子树的最大的前缀和为p.m,我们可以递推算出p.m的值。
p.m=Max{
p.left.m; //最大前缀和的尾元素在左子树
p.left.s+p.w; //最大前缀和的尾元素就是p
p.left.s+p.w+p.right.m; //最大前缀和的尾元素在右子树
}
于是全部序列的最大前缀和就是根节点root.m。
于是得到的算法如下:
- 建立离散化坐标系;
- 左右扫描,确定带状区间,维护平衡树中节点;
- 统计对于确定带状区间,平衡树中元素最大的前缀和;
/*
* Problem: POI2001 kop
* Author: Guo Jiabao
* Time: 2009.2.7 16:16
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=15001;
struct point{int x,y;};
struct linknode{int s;linknode *next;};
class Treap_node
{
public:
Treap_node *left,*right;
int fix,weight,sum,m,key;
Treap_node(int tk,int w):key(tk),weight(w),sum(w),m(w){fix=rand();left=right=0;}
inline int leftsum (){return left ?left ->sum:0;}
inline int rightsum(){return right?right->sum:0;}
};
int H,W;//区域高度 宽度
int N,L,Lc=-1,MaxAns;
int D[MAXN];
point P[MAXN];
linknode LS[MAXN],*Line[MAXN];
Treap_node *Treap_root;
void Treap_Rotate_Right(Treap_node *&p)
{
Treap_node *q=p->left;
q->sum+=p->rightsum()+p->weight;
p->sum=q->rightsum()+p->rightsum()+p->weight;
p->left=q->right;
q->right=p;
p=q;
}
void Treap_Rotate_Left(Treap_node *&p)
{
Treap_node *q=p->right;
q->sum+=p->leftsum()+p->weight;
p->sum=q->leftsum()+p->leftsum()+p->weight;
p->right=q->left;
q->left=p;
p=q;
}
void Treap_maintain(Treap_node *&p)
{
int lm,ls,rm;
lm=ls=rm=0;
if (p->left)
lm=p->left->m,ls=p->left->sum;
if (p->right)
rm=p->right->m;
p->m=lm;
if (ls + p->weight > p->m) p->m = ls + p->weight;
if (ls + p->weight + rm > p->m) p->m=ls + p->weight + rm;
}
void Treap_edit(Treap_node *&p,int v,int delta)
{
if (!p)
p=new Treap_node(v,delta);
else
{
if ( v < p->key )
{
p->sum+=delta;
Treap_edit(p->left,v,delta);
if (p->left && p->left->fix < p->fix)
{
Treap_Rotate_Right(p);
Treap_maintain(p->right);
}
Treap_maintain(p);
}
else if ( v > p->key )
{
p->sum+=delta;
Treap_edit(p->right,v,delta);
if (p->right && p->right->fix < p->fix)
{
Treap_Rotate_Left(p);
Treap_maintain(p->left);
}
Treap_maintain(p);
}
else
{
p->weight+=delta;
p->sum+=delta;
Treap_maintain(p);
}
}
}
void linktable_ins(linknode *&p,int v)
{
if (p)
{
linknode *t=p;
p=&LS[++Lc];
p->next=t;
}
else
p=&LS[++Lc];
LS[Lc].s=v;
}
void init()
{
freopen("kop.in","r",stdin);
freopen("kop.out","w",stdout);
scanf("%d%d%d",&W,&H,&N);
for (int i=1;i<=N;i++)
scanf("%d%d",&P[i].x,&P[i].y);
}
inline int cmp(const void *a,const void *b)
{
return ((point *)a)->x - ((point *)b)->x;
}
void discrete() //离散化横坐标 建立链表
{
int i,lastv=-1;
qsort(P+1,N,sizeof(P[0]),cmp);
L=0;
for (i=1;i<=N;i++)
{
if (P[i].x!=lastv)
{
lastv=P[i].x;
D[++L]=P[i].x;
linktable_ins(Line[L],P[i].y);
}
else
linktable_ins(Line[L],P[i].y);
}
}
void RemoveLine(int p)
{
for (linknode *k=Line[p];k;k=k->next)
{
Treap_edit(Treap_root,k->s,-1);
Treap_edit(Treap_root,k->s+H+1,1);
}
}
void AddLine(int p)
{
for (linknode *k=Line[p];k;k=k->next)
{
Treap_edit(Treap_root,k->s,1);
Treap_edit(Treap_root,k->s+H+1,-1);
}
}
void scanx() //横向扫描 确定区间
{
int Lb,Rb;
AddLine(1);
for (Lb=Rb=1;Rb<L && Lb<=L;)
{
while (Rb+1<=L && D[Rb+1]-D[Lb]<=W)
AddLine(++Rb);
if (Treap_root->m>MaxAns)
MaxAns=Treap_root->m;
RemoveLine(Lb++);
}
}
void solve()
{
discrete();
scanx();
printf("%d",MaxAns);
}
int main()
{
init();
solve();
return 0;
}
<h2><span class="mw-headline">金矿 </span></h2>
问题描述
金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作,决定在一块包含 n(n ≤ 15000) 个采金点的长方形土地中划出一块长度为 S ,宽度为 W 的区域奖励给他(1 ≤ s , w ≤ 10 000)。老师傅可以自己选择这块地的位置,显然其 中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上,它也应当被计算在内。
输入格式
输入文件的第一行有两个整数,中间用一个空格隔开,表示长方形土地的长和宽即s和w(1<=s,w<=10 000)。第二行有一个整数n(1<=n<=15 000),表示金矿数量。下面的n行与金矿相对应,每行两个整数x和y (-30 000<=x,y<=30 000),中间用一个空格隔开,表示金矿的坐标。
输出格式
输出文件只有一个整数,表示选择的最大金矿的数。
输入样例
1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2
输出样例
4
上次修改时间 2017-05-22