问题描述
金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定在一块包含 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),中间用一个空格隔开，表示金矿的坐标。
输出格式
输出文件只有一个整数，表示选择的最大金矿的数。
------------------------------------------------------------
正解=离散化+平衡树
点比坐标小的多，离散之- =
要求一个宽 s 长 w的且覆盖点最多的矩形
维护一个宽度为 s 的带状区间 既满足宽度限制
建立以y为关键字的平衡树维护之
我们要求的既长度h的区间中的最大值
将一个点x,y 拆成两个点
x,y,权值为1
x,y+h+1权值为-1
维护一个这样的以y为第一关键字，权值为第二关键字的平衡树
最大前缀和既长度h的区间中的最大值（Orz神差分前缀求和）
代码如下：
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
#define INF 999999999
#define Min(num1,num2) if(num1>num2) num1=num2
#define Max(num1,num2) if(num1<num2) num1=num2
#define N 150000
using namespace std ;
struct Point {
int x,y,neg,pos;
}point[N];
bool cmp(const Point &X,const Point &Y){
return X.x<Y.x;
}
struct Tree{
int l,r,f,v1,v2,sum,mmax;
}a[N];
int n,Root,Total,s,w,edge[N],top;
int q[];
void puit(int now){
printf("No.%d L:%d R:%d V1:%d V2:%d Sum:%d Mmax:%d\n",now,a[now].l,a[now].r,a[now].v1,a[now].v2,a[now].sum,a[now].mmax);
}
void update(int now){
// puit(now);
// printf("->\n");
// puit(a[now].l);
// puit(a[now].r);
// printf("-------------------------------\n");
a[now].sum=a[a[now].l].sum+a[a[now].r].sum+a[now].v2;
a[now].mmax=max(a[a[now].l].mmax,a[a[now].l].sum+a[now].v2 );
a[now].mmax=max(a[now].mmax ,a[a[now].l].sum+a[now].v2+a[a[now].r].mmax);
}
void put(int now){
if(a[now].l) put(a[now].l);
printf("%d ",a[now].v1);
//printf("V1%d(V2%d)(Sum%d)(Mmax%d) ",a[now].v1,a[now].v2,a[now].sum,a[now].mmax);
if(a[now].r) put(a[now].r);
}
void rig(int now){
int f=a[now].f;
a[now].f=a[f].f;
if(a[a[f].f].l==f) a[a[f].f].l=now;
if(a[a[f].f].r==f) a[a[f].f].r=now;
a[f].f=now;
a[f].l=a[now].r;
a[a[now].r].f=f;
a[now].r=f;
update(f);
}
void lef(int now){
int f=a[now].f;
a[now].f=a[f].f;
if(a[a[f].f].l==f) a[a[f].f].l=now;
if(a[a[f].f].r==f) a[a[f].f].r=now;
a[f].f=now;
a[f].r=a[now].l;
a[a[now].l].f=f;
a[now].l=f;
update(f);
}
void splay(int now,int F=){
while(a[now].f!=F){
int f=a[now].f;
int ff=a[f].f;
if(ff==F)
if(a[f].l==now)
rig(now);
else
lef(now);
else
if(a[ff].l==f)
if(a[f].l==now)
rig(f),rig(now);
else
lef(now),rig(now);
else
if(a[f].r==now)
lef(f),lef(now);
else
rig(now),lef(now);
}
update(now);
if(!F) Root=now;
}
int insert(int v1,int v2){
for(int now=Root;;){
q[++top]=now;
if(v1<a[now].v1||(v1==a[now].v1&&v2<=a[now].v2))
if(a[now].l) now=a[now].l;
else{
a[now].l=++Total;
a[Total].v1=v1;
a[Total].v2=v2;
a[Total].f=now;
a[Total].sum=v2;
a[Total].mmax=max(v2,);
break;
}
else
if(a[now].r) now=a[now].r;
else{
a[now].r=++Total;
a[Total].v1=v1;
a[Total].v2=v2;
a[Total].f=now;
a[Total].sum=v2;
a[Total].mmax=max(v2,);
break;
}
}
while(top) update(q[top--]);
splay(Total);
// put(Root);
// printf("\n");
return Total;
}
int prev(int now){
splay(now);
now=a[now].l;
while(a[now].r) now=a[now].r;
return now;
}
int succ(int now){
splay(now);
now=a[now].r;
while(a[now].l) now=a[now].l;
return now;
}
void del(int now){
int start=prev(now);
int end=succ(now);
splay(start);
splay(end,Root);
a[a[Root].r].l=;
update(a[Root].r);
update(Root);
}
void removeL(int now){
del(point[now].pos);
del(point[now].neg);
}
void removeR(int now){
point[now].pos=insert(point[now].y ,);
point[now].neg=insert(point[now].y+w+,-);
}
int main(){
scanf("%d%d%d",&s,&w,&n);
for(int i=;i<=n;i++)
scanf("%d%d",&point[i].x,&point[i].y);
sort(point+,point++n,cmp);
point[].x=-INF;
int Maxedge=;
for(int i=;i<=n;i++)
if(point[i].x!=point[i-].x)
edge[++Maxedge]=point[i].x;
int L=,now=,R=,ans=;
Total=;
Root=;
a[].v1=INF;
a[].v1=-INF;
a[].l=;
a[].f=;
while(now<Maxedge){
++now;
while(edge[now]-point[L].x>s&&L <=n) removeL(L),++L;
while(point[R].x==edge[now] &&R <=n) removeR(R),++R;
Max(ans,a[Root].mmax); }
printf("%d",ans);
}