Bzoj2244 [SDOI2011]拦截导弹

Time Limit: 30 Sec Memory Limit: 512 MBSec Special Judge
Submit: 561 Solved: 228

Description

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

Input

第一行包含一个正整数n，表示敌军导弹数量；

下面行按顺序给出了敌军所有导弹信息：

第i+1行包含2个正整数h_i和v_i，分别表示第枚导弹的高度和速度。

Output

输出包含两行。

第一行为一个正整数，表示最多能拦截掉的导弹数量；

第二行包含n个0到1之间的实数，第i个数字表示第i枚导弹被拦截掉的概率（你可以保留任意多位有效数字）。

Sample Input

4

3 30

4 40

6 60

3 30

Sample Output

2

0.33333 0.33333 0.33333 1.00000

【数据规模和约定】

对于100%的数据，1≤n≤5*104， 1≤hi ，vi≤109；

均匀分布着约30%的数据，所有vi均相等。

均匀分布着约50%的数据，满足1≤hi ，vi≤1000。

HINT

鸣谢kac提供sj程序！

Source

第一轮day2

CDQ分治 DP

就是因为导弹拦截系统毛病都这么多，我推COD9的时候才会打出来BAD END

传说这叫三维偏序问题（求三个维度上都单调的序列）

如果一颗导弹在最长序列上，那么包含它的最长序列数量/所有的最长序列数量就是它被拦截掉的概率

先把高度和速度都离散化。

用CDQ分治除掉时间维度，分治过程中排序除掉高度，然后用树状数组求LIC←（为了能用树状数组，首先要将速度逆序，把单调降转化成单调升）

然后将所有数组逆序，再用CDQ分治求一遍最长单调序列。

处理每一颗导弹，如果它前面的最长序列长度+它后面的最长序列长度（当然是包含它自身的序列）+自身的1 ==最长单调不升序列长度，那么它在(前面的方案数*后面的方案数)个最长序列上。

好麻烦好麻烦

掏出了先前的CDQ分治模板一点点写，终于搞定了。

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 using namespace std;
  9 const int mxn=50021;
 10 int read(){
 11     int x=0,f=1;char ch=getchar();
 12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 14     return x*f;
 15 }
 16 struct BIT{
 17     int f;
 18     double w;
 19     BIT(){f=0,w=0;}
 20 }t[mxn];
 21 int n;
 22 int st[mxn],top=0;
 23 void add(int p,int f,double w){
 24     while(p<n){
 25         if(t[p].f<f){
 26             if(t[p].f==0)st[++top]=p;
 27             t[p].f=f;t[p].w=w;
 28         }
 29         else if(t[p].f==f) t[p].w+=w;
 30         p+=p&-p;
 31     }
 32     return;
 33 }
 34 BIT ask(int p){
 35     BIT res;
 36     while(p){
 37         if(t[p].f>res.f) res=t[p];
 38         else if(t[p].f==res.f) res.w+=t[p].w;
 39         p-=p&-p;
 40     }
 41     return res;
 42 }
 43 //
 44 struct Dan{
 45     int h,v;
 46     int f[2];
 47     double g[2];//正/反 最长长度 对应方案数 
 48     int id,t;
 49 }a[mxn],q[mxn];
 50 int wh[mxn],wv[mxn],id[mxn];
 51 int rk[mxn];
 52 int cmp(int i,int j){
 53     return a[i].h<a[j].h || (a[i].h==a[j].h && a[i].id<a[j].id);
 54 }
 55 int cmpid(Dan a,Dan b){return a.id<b.id;}
 56 //
 57 int cnt=0;
 58 void solve(int l,int r,int mode){
 59     if(l==r){
 60         if(a[l].f[mode]<1){a[l].f[mode]=1;a[l].g[mode]=1;}
 61         return;
 62     }
 63     int mid=(l+r)>>1,i,j;
 64     memcpy(q+l,a+l,sizeof(Dan)*(r-l+1));
 65     int q1=l,q2=mid+1;
 66     for(i=l;i<=r;i++){//按高度划分 
 67         if(q[i].t<=mid)a[q1++]=q[i];     else a[q2++]=q[i];
 68     }
 69     solve(l,mid,mode);
 70     q1=l;
 71     for(i=mid+1;i<=r;i++){
 72         while(q1<=mid && a[q1].id<a[i].id) add(a[q1].v,a[q1].f[mode],a[q1].g[mode]),q1++;
 73         BIT res=ask(a[i].v);
 74         if(!res.f)continue;
 75 //      printf("!! %d   %.3f
",res.f,res.w);
 76         if(res.f+1>a[i].f[mode]){
 77             a[i].f[mode]=res.f+1;
 78             a[i].g[mode]=res.w;
 79         }
 80         else if(res.f+1==a[i].f[mode]) a[i].g[mode]+=res.w;
 81     }
 82 //  for(i=1;i<=n;i++) t[i].w=0,t[i].f=0;//可优化 
 83     while(top){t[st[top]].w=0;t[st[top--]].f=0;}
 84     solve(mid+1,r,mode);
 85     merge(a+l,a+mid+1,a+mid+1,a+r+1,q+l,cmpid);//
 86     memcpy(a+l,q+l,sizeof(Dan)*(r-l+1));//还原 
 87     return;
 88 }
 89 int th,tv=0;
 90 int main(){
 91 //  freopen("in.txt","r",stdin);
 92     int i,j;
 93     n=read();
 94     for(i=1;i<=n;i++){
 95         a[i].h=read();a[i].v=read();a[i].id=i;
 96         wh[i]=a[i].h;wv[i]=a[i].v;
 97         rk[i]=i;
 98     }
 99     sort(wh+1,wh+n+1);
100     sort(wv+1,wv+n+1);
101     th=unique(wh+1,wh+n+1)-wh-1;
102     tv=unique(wv+1,wv+n+1)-wv-1;
103     for(i=1;i<=n;i++){//离散化 倒序 
104         a[i].h=th-(lower_bound(wh+1,wh+th+1,a[i].h)-wh)+1;
105         a[i].v=tv-(lower_bound(wv+1,wv+tv+1,a[i].v)-wv)+1;
106     }
107     sort(rk+1,rk+n+1,cmp);
108     for(i=1;i<=n;i++) a[rk[i]].t=i;
109     solve(1,n,0);
110     for(i=1;i<=n;i++){
111         a[i].h=th-a[i].h+1;
112         a[i].v=tv-a[i].v+1;
113         a[i].id=n-a[i].id+1;
114         a[i].t=n-a[i].t+1;
115     }
116     reverse(a+1,a+n+1);
117 //  sort(rk+1,rk+n+1,cmp);
118     solve(1,n,1);
119     reverse(a+1,a+n+1);
120     double smm=0;int ans=0;
121     for(register int i=1;i<=n;i++){
122         if(a[i].f[0]+a[i].f[1]-1>ans){ans=a[i].f[0]+a[i].f[1]-1;}
123     }
124     printf("%d
",ans);
125     for(i=1;i<=n;i++){
126         if(a[i].f[0]==ans){
127             smm+=a[i].g[0]*a[i].g[1];
128         }
129     }
130     for(i=1;i<=n;i++){
131         double res=a[i].g[0]*a[i].g[1];
132         if(a[i].f[0]+a[i].f[1]-1!=ans)printf("0 ");
133         else printf("%.5f ",res/smm);
134     }
135     return 0;
136 }