cdq。。还真是。。
一开始自己写，设f[i]为以i结尾的最优方案，fn[i]为以i结尾的最优方案数，然后cdq完了第一问就出来了，还顺便把总最优方案数算了，
and then？ mengbier
然后各路%啊，一个下午+一晚上就交代了
怎么做呢？我们再cdq出另一个f和fn表示以i开头的最优方案和方案数
然后想一想i在这 l——————i——————r
然后 f[0][i]就是l~i的最优方案了，f[1][i]就是i~r的最优方案
那么两个一合并，再减去重复计算的i位置，假如等于最优方案，说明i出现了fn[0][i]*fn[1][i]（一一组合嘛）
完成。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long double LD; int n; int s[51000];LD g[51000]; int lowbit(int x){return x&-x;} void change(int x,int k,LD fan) { while(x<=50500) { if(s[x]<k) { s[x]=k; g[x]=fan; } else if(s[x]==k)g[x]+=fan; x+=lowbit(x); } } void clean(int x) { while(x<=50500) { s[x]=0;g[x]=0; x+=lowbit(x); } } int getmax(int x,LD &fan) { int ret=0;fan=0; while(x>=1) { if(s[x]>ret) { ret=s[x]; fan=g[x]; } else if(s[x]==ret)fan+=g[x]; x-=lowbit(x); } return ret; } struct node { int x,y,z; }a[51000],b[51000]; bool cmpx(node n1,node n2){return n1.x<n2.x;} bool cmpx2(node n1,node n2){return n1.x>n2.x;} bool cmpy(node n1,node n2){return n1.y>n2.y;} bool cmpy2(node n1,node n2){return n1.y<n2.y;} int lslen,ls[51000]; void LSH() { lslen=0; for(int i=1;i<=n;i++)ls[++lslen]=a[i].y; sort(ls+1,ls+lslen+1); lslen=unique(ls+1,ls+lslen+1)-ls-1; for(int i=1;i<=n;i++) a[i].y=lower_bound(ls+1,ls+lslen+1,a[i].y)-ls; lslen=0; for(int i=1;i<=n;i++)ls[++lslen]=a[i].z; sort(ls+1,ls+lslen+1); lslen=unique(ls+1,ls+lslen+1)-ls-1; for(int i=1;i<=n;i++) a[i].z=lower_bound(ls+1,ls+lslen+1,a[i].z)-ls, a[i].z=n-a[i].z+1; } int f[2][51000];LD fn[2][51000]; void cdq(int l,int r) { if(l==r)return ; int mid=(l+r)/2; cdq(l,mid); sort(a+mid+1,a+r+1,cmpy); int tp=l; for(int i=mid+1;i<=r;i++) { while(tp<=mid&&(a[tp].y>=a[i].y)) change(a[tp].z,f[0][a[tp].x],fn[0][a[tp].x]), tp++; LD fan; int d=getmax(a[i].z,fan)+1; if(d>f[0][a[i].x]) { f[0][a[i].x]=d; fn[0][a[i].x]=fan; } else if(d==f[0][a[i].x])fn[0][a[i].x]+=fan; } for(int i=l;i<=mid;i++)clean(a[i].z); sort(a+mid+1,a+r+1,cmpx); cdq(mid+1,r); sort(a+l,a+r+1,cmpy); } void cdq2(int l,int r) { if(l==r)return ; int mid=(l+r)/2; cdq2(l,mid); sort(a+mid+1,a+r+1,cmpy2); int tp=l; for(int i=mid+1;i<=r;i++) { while(tp<=mid&&a[tp].y<=a[i].y) change(a[tp].z,f[1][a[tp].x],fn[1][a[tp].x]), tp++; LD fan; int d=getmax(a[i].z,fan)+1; if(d>f[1][a[i].x]) { f[1][a[i].x]=d; fn[1][a[i].x]=fan; } else if(d==f[1][a[i].x])fn[1][a[i].x]+=fan; } for(int i=l;i<=mid;i++)clean(a[i].z); sort(a+mid+1,a+r+1,cmpx2); cdq2(mid+1,r); sort(a+l,a+r+1,cmpy2); } LD cao[51000]; int main() { freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) a[i].x=i, scanf("%d%d",&a[i].y,&a[i].z); LSH(); for(int i=1;i<=n;i++)b[i]=a[i]; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++)f[0][i]=1,fn[0][i]=1; cdq(1,n); int mmax=0;LD sum=0; for(int i=1;i<=n;i++) if(f[0][i]>mmax) { mmax=f[0][i]; sum=fn[0][i]; } else if(mmax==f[0][i])sum+=fn[0][i]; printf("%d ",mmax); for(int i=1;i<=n;i++)a[i]=b[n-i+1]; for(int i=1;i<=n;i++)a[i].z=n-a[i].z+1; for(int i=1;i<=n;i++)f[1][i]=1,fn[1][i]=1; cdq2(1,n); for(int i=1;i<=n;i++) if(f[0][i]+f[1][i]-1==mmax) cao[i]=fn[0][i]*fn[1][i]; for(int i=1;i<n;i++)printf("%.5Lf ",cao[i]/sum); printf("%.5Lf ",cao[n]/sum); return 0; }