拦截导弹
【问题描述】
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都
不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导
弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最
多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机
选取一个作为最终的拦截导弹行动蓝图。
我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚
导弹被拦截掉的概率。
【输入格式】
第一行包含一个正整数，表示敌军导弹数量；
下面行按顺序给出了敌军所有导弹信息：
第行包含个正整数和，分别表示第枚导弹的高度和速度。
【输出格式】
输出包含两行。
第一行为一个正整数，表示最多能拦截掉的导弹数量；
第二行包含个0 到1 之间的实数，第个数字表示第枚导弹被拦截掉的概率（你可以保留任
意多位有效数字）。
【样例输入】
4
3 30
4 40
6 60
3 30
【样例输出】
2
0.33333 0.33333 0.33333 1.00000
【数据规模和约定】
n<=50000
1<=h,v<=10^9
线段树套线段树
设f[i]为打到这一颗导弹的最长长度
按导弹的顺序扫描，f[i]的取值则为线段树套线段树中满足条件的最大值+1
这样便可以求出来最大值
求出f数组之后，把导弹按f[i]为第一关键字，i为第二关键字排序
用pro[i]表示取了该值之后右边的方案数有多少
按f的取值分阶段扫描，每扫描到一个i，将上一阶段所有大于i的导弹的方案数插入线段树
本阶段扫描完成，将上阶段的导弹全部删除，我采取了插入负数的方式
再用ble[i]表示取了该值左边的方案数有多少种，求的方法类似其pro的方法
每个导弹被打过的概率为(pre[i]*ble[i]/总方案数)
这里对精度要求并不高，而且方案数可能会爆int64，所以采用了extended来存储pre和ble
这个h和v的取值为[1,10^9]，我本认为(log(10^9))^2跟(log(10^5))^2差的不是很多，虽然确实差的不算多900跟256的差别……
但线段树不离散化会超时还要爆内存，所以加入离散化
写了9个k
program missile;
var
w,o,s,e,ans,all,tot,n,i,j,k:longint;
sa:extended;
quick,new:array [0..100001] of longint;
ble,pro:array [0..50001] of extended;
dl,v,h,f:array [0..50001] of longint;
left,right,root:array [0..1000001] of longint;
lef,rig,point:array [0..10000001] of longint;
sum:array [0..10000001] of extended;
procedure swap (var a,b:longint);inline;
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure insert1(vi,p,l,r,now:longint;o:extended);
var
mid:longint;
begin
sum[now]:=sum[now]+o;
if point[now]<p then point[now]:=p;
if l=r then exit;
mid:=(l+r) div 2;
if vi<=mid then
begin
if lef[now]=0 then
begin
inc(all);
lef[now]:=all;
end;
insert1(vi,p,l,mid,lef[now],o);
end
else
begin
if rig[now]=0 then
begin
inc(all);
rig[now]:=all;
end;
insert1(vi,p,mid+1,r,rig[now],o);
end;
end;
procedure insert (hi,vi,p,l,r,now:longint;o:extended);
var
mid:longint;
begin
if root[now]=0 then
begin
inc(all);
root[now]:=all;
end;
insert1(vi,p,1,w+1,root[now],o);
if l=r then exit;
mid:=(l+r) div 2;
if hi<=mid then
begin
if left[now]=0 then
begin
inc(tot);
left[now]:=tot;
end;
insert(hi,vi,p,l,mid,left[now],o);
end
else
begin
if right[now]=0 then
begin
inc(tot);
right[now]:=tot;
end;
insert(hi,vi,p,mid+1,r,right[now],o);
end;
end;
function find1 (vi,l,r,now:longint):longint;
var
ans,k,mid:longint;
begin
if vi=l then exit(point[now]);
mid:=(l+r) div 2;
if vi>mid then
if rig[now]=0 then exit(0)
else exit(find1(vi,mid+1,r,rig[now]))
else
begin
ans:=0;
if lef[now]=0 then k:=0
else k:=find1(vi,l,mid,lef[now]);
if ans<k then ans:=k;
if rig[now]=0 then k:=0
else k:=find1(mid+1,mid+1,r,rig[now]);
if k>ans then ans:=k;
exit(ans);
end;
end;
function find(hi,vi,l,r,now:longint):longint;
var
ans,k,mid:longint;
begin
if hi=l then
if root[now]=0 then exit(0)
else exit(find1(vi,1,w+1,root[now]));
mid:=(l+r) div 2;
if hi>mid then
if right[now]=0 then exit(0)
else exit(find(hi,vi,mid+1,r,right[now]))
else
begin
ans:=0;
if left[now]=0 then k:=0
else k:=find(hi,vi,l,mid,left[now]);
if k>ans then ans:=k;
if right[now]=0 then k:=0
else k:=find(mid+1,vi,mid+1,r,right[now]);
if k>ans then ans:=k;
exit(ans);
end;
end;
function solve1 (vi,l,r,now:longint):extended;
var
mid:longint;
ans:extended;
begin
if vi=r then exit(sum[now]);
mid:=(l+r) div 2;
if vi<=mid then
if lef[now]=0 then exit(0)
else exit(solve1(vi,l,mid,lef[now]))
else
begin
ans:=0;
if lef[now]<>0 then ans:=ans+solve1(mid,l,mid,lef[now]);
if rig[now]<>0 then ans:=ans+solve1(vi,mid+1,r,rig[now]);
exit(ans);
end;
end;
function solve (hi,vi,l,r,now:longint):extended;
var
mid:longint;
ans:extended;
begin
if r=hi then
if root[now]=0 then exit(0)
else exit(solve1(vi,1,w+1,root[now]));
mid:=(l+r) div 2;
if hi<=mid then
if left[now]=0 then exit(0)
else exit(solve(hi,vi,l,mid,left[now]))
else
begin
ans:=0;
if left[now]<>0 then ans:=ans+solve(mid,vi,l,mid,left[now]);
if right[now]<>0 then ans:=ans+solve(hi,vi,mid+1,r,right[now]);
exit(ans);
end;
end;
function doit1 (vi,l,r,now:longint):extended;
var
mid:longint;
ans:extended;
begin
if l=vi then exit(sum[now]);
mid:=(l+r) div 2;
if vi>mid then
if rig[now]=0 then exit(0)
else exit(doit1(vi,mid+1,r,rig[now]))
else
begin
ans:=0;
if lef[now]<>0 then ans:=ans+doit1(vi,l,mid,lef[now]);
if rig[now]<>0 then ans:=ans+doit1(mid+1,mid+1,r,rig[now]);
exit(ans);
end;
end;
function doit (hi,vi,l,r,now:longint):extended;
var
mid:longint;
ans:extended;
begin
if l=hi then
if root[now]=0 then exit(0)
else exit(doit1(vi,1,w+1,root[now]));
mid:=(l+r) div 2;
if hi>mid then
if right[now]=0 then exit(0)
else exit(doit(hi,vi,mid+1,r,right[now]))
else
begin
ans:=0;
if left[now]<>0 then ans:=ans+doit(hi,vi,l,mid,left[now]);
if right[now]<>0 then ans:=ans+doit(mid+1,vi,mid+1,r,right[now]);
exit(ans);
end;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while (f[dl[i]]<f[k])or((f[dl[i]]=f[k])and(dl[i]<k)) do inc(i);
while (f[dl[j]]>f[k])or((f[dl[j]]=f[k])and(dl[j]>k)) do dec(j);
if i>j then break;
swap(dl[i],dl[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
procedure qsort1 (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=quick[(s+e) div 2];
while i<=j do
begin
while quick[i]<k do inc(i);
while quick[j]>k do dec(j);
if i>j then break;
swap(quick[i],quick[j]);
inc(i);
dec(j);
end;
qsort1(s,j);
qsort1(i,e);
end;
function convert (now:longint):longint;inline;
var
s,e,mid:longint;
begin
s:=1;
e:=w;
while s<>e do
begin
mid:=(s+e) div 2;
if new[mid]=now then exit(mid)
else
if new[mid]>now then e:=mid-1
else s:=mid+1;
end;
exit(s);
end;
begin
assign(input,'missile.in');
reset(input);
assign(output,'missile.out');
rewrite(output);
read(n);
for i:=1 to n do
begin
read(h[i],v[i]);
quick[2*i-1]:=h[i];
quick[2*i]:=v[i];
end;
qsort1(1,2*n);
w:=0;
i:=1;
while i<=2*n do
begin
k:=i;
while quick[i]=quick[k] do inc(i);
inc(w);
new[w]:=quick[k];
end;
for i:=1 to n do
begin
h[i]:=convert(h[i]);
v[i]:=convert(v[i]);
end;
ans:=1;
for i:=1 to n do
begin
f[i]:=find(h[i],v[i],1,w+1,0)+1;
insert(h[i],v[i],f[i],1,w+1,0,0);
if f[i]>ans then ans:=f[i];
dl[i]:=i;
end;
writeln(ans);
tot:=0;
all:=0;
fillchar(left,sizeof(left),0);
fillchar(right,sizeof(right),0);
fillchar(lef,sizeof(lef),0);
fillchar(rig,sizeof(rig),0);
fillchar(root,sizeof(root),0);
qsort(1,n);
h[n+1]:=1;
v[n+1]:=1;
f[n+1]:=ans+1;
pro[n+1]:=1;
h[0]:=w+1;
v[0]:=w+1;
f[0]:=0;
dl[n+1]:=n+1;
s:=n+1;
e:=n+1;
i:=n;
while i>=0 do
begin
k:=i;
j:=e;
while (i>=0)and(f[dl[i]]=f[dl[k]]) do
begin
while (j>=s)and(dl[j]>dl[i]) do
begin
insert(h[dl[j]],v[dl[j]],-1,1,w+1,0,pro[dl[j]]);
dec(j);
end;
pro[dl[i]]:=solve(h[dl[i]],v[dl[i]],1,w+1,0);
dec(i);
end;
for o:=j+1 to e do
insert(h[dl[o]],v[dl[o]],-1,1,w+1,0,-pro[dl[o]]);
e:=s-1;
s:=i+1;
end;
tot:=0;
all:=0;
fillchar(left,sizeof(left),0);
fillchar(right,sizeof(right),0);
fillchar(lef,sizeof(lef),0);
fillchar(rig,sizeof(rig),0);
fillchar(root,sizeof(root),0);
fillchar(sum,sizeof(sum),0);
s:=0;
e:=0;
ble[0]:=1;
i:=1;
while i<=n+1 do
begin
k:=i;
j:=s;
while (i<=n+1)and(f[dl[i]]=f[dl[k]]) do
begin
while (j<=e)and(dl[j]<dl[i]) do
begin
if pro[dl[j]]>0.1 then
insert(h[dl[j]],v[dl[j]],-1,1,w+1,0,ble[dl[j]]);
inc(j);
end;
if pro[dl[i]]>0.1 then
ble[dl[i]]:=doit(h[dl[i]],v[dl[i]],1,w+1,0);
inc(i);
end;
for o:=s to j-1 do
if pro[dl[o]]>0.1 then
insert(h[dl[o]],v[dl[o]],-1,1,w+1,0,-ble[dl[o]]);
s:=e+1;
e:=i-1;
end;
for i:=1 to n do
write(abs(pro[i]*ble[i]/pro[0]):0:5,' ');
writeln;
close(input);
close(output);
end.