采矿(KOP)
金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定送他一块长方形地。长度为S，宽度为W。老师傅可以自己选择这块地。显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内。
任务：
读入采金点的位置。计算最大的价值。
输入：
文件KOP.IN的第一行是S和W，(1<=s,w<=10 000);他们分别平行于OX坐标和OY坐标，指明了地域的尺寸。接下来一行是整数n (1<=n<=15 000)，表示采金点的总数。然后是n行，每行两个整数，给出了一个采金点的坐标。坐标范围是(-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
果然POI的题目真是经典,在看题解时学到了很多的东西 也是从黑书中寻觅到的
运用到的知识很多,却很清晰
其中一些技巧看似很简单却十分巧妙
这时我才感觉到二叉排序树强大之处
而更详细的题解方法 参见<二分法与统计问题>李睿神牛
#include<cstdio>
#define maxn 15005
#define max(a,b) ((a)>(b)?(a):(b))
int n,m,s,w,num,ans,x[2*maxn],y[2*maxn],yy[2*maxn];
struct {
int y,sum,maxsum;
}t[4*maxn]; void qsX(int,int);
void qsY(int,int);
void buildtree(int);
void ins(int,int,int); int main(){
FILE *in=fopen("kop.in","r");
FILE *out=fopen("kop.out","w");
int i,j,k;
for(i=0;i<=4*maxn-1;i++) t[i].y=-30001;
fscanf(in,"%d%d%d",&s,&w,&n);
for(i=1;i<=n;i++){
fscanf(in,"%d%d",&x[i],&y[i]);
yy[i]=y[i];
yy[n+i]=y[i]+w+1;
}
yy[2*n+1]=-30001;
qsY(1,2*n);
m=0;
for(i=1;i<=2*n;i++)
if(yy[i]!=yy[i+1]) yy[++m]=yy[i];
num=0;
buildtree(1);
qsX(1,n);
i=1;j=1;k=x[j];
while(i<=n&&j<=n){
while(x[i]<=k+s&&i<=n){
ins(1,y[i],1);
ins(1,y[i]+w+1,-1);
i++;
}
if(ans<t[1].maxsum) ans=t[1].maxsum;
while(x[j]==k&&j<=n){
ins(1,y[j],-1);
ins(1,y[j]+w+1,1);
j++;
}
k=x[j];
}
fprintf(out,"%d",ans);
fclose(in);fclose(out);
return 0;
} void qsX(int l,int r){
int i=l,j=r,k=x[(l+r)/2],t;
do{
while(x[i]<k) ++i;
while(x[j]>k) --j;
if(i<=j){
t=x[i];x[i]=x[j];x[j]=t;
t=y[i];y[i]=y[j];y[j]=t;
++i;--j;
}
}while(i<j);
if(i<r) qsX(i,r);
if(j>l) qsX(l,j);
}
void qsY(int l,int r){
int i=l,j=r,k=yy[(l+r)/2],t;
do{
while(yy[i]<k) ++i;
while(yy[j]>k) --j;
if(i<=j){
t=yy[i];yy[i]=yy[j];yy[j]=t;
++i;--j;
}
}while(i<j);
if(i<r) qsY(i,r);
if(j>l) qsY(l,j);
}
void buildtree(int now){
if(2*now<=m) buildtree(2*now);
t[now].y=yy[++num];
t[now].sum=t[now].maxsum=0;
if(2*now+1<=m) buildtree(2*now+1);
}
void ins(int now,int num,int p){
if(num<t[now].y) ins(now*2,num,p);
if(num>t[now].y) ins(now*2+1,num,p);
t[now].sum+=p;
t[now].maxsum=max(t[now*2].maxsum,max(t[now].sum-t[now*2+1].sum,t[now].sum-t[now*2+1].sum+t[now*2+1].maxsum));
}