题解：
对于第一问，我们求二维LIS即可;
对于第二问，我们可以记录向前最长长度，向前最长方案数，向后最长长度，向后最长方案数。
其实改改树状数组即可。
还有，方案数一定要开double。
代码：
#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 50050 inline int rd() { int f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n; struct node { int h,v,s,f,g; double w1,w2; }p[N],tmp[N]; bool cmph(node a,node b) { return a.h>b.h; } bool cmpH(node a,node b) { return a.h<b.h; } bool cmps(node a,node b) { return a.s<b.s; } struct pR { int x,y; }ph[N],pv[N]; struct Pair { int x; double y; Pair(){x=0,y=0.0;} Pair(int x,double y):x(x),y(y){} }; bool cmp(pR a,pR b) { return a.x<b.x; } struct BIT { Pair v[N]; void up(int x,int d,double c) { while(x<N) { if(v[x].x<d)v[x]=Pair(d,c); else if(v[x].x==d)v[x].y+=c; x+=(x&-x); } } void clear(int x) { while(x<N&&v[x].x) { v[x]=Pair(0,0.0); x+=(x&-x); } } Pair down(int x) { Pair ret; while(x) { if(v[x].x>ret.x)ret=v[x]; else if(v[x].x==ret.x)ret.y+=v[x].y; x-=(x&-x); } return ret; } }tr; int max_v; void cdq(int l,int r) { if(l==r)return ; int mid = (l+r)>>1; cdq(l,mid); sort(p+l,p+mid+1,cmph); sort(p+mid+1,p+r+1,cmph); int i,j; for(i=mid+1,j=l;i<=r;i++) { while(j<=mid&&p[i].h<=p[j].h) { tr.up(max_v-p[j].v,p[j].f,p[j].w1); j++; } Pair tm = tr.down(max_v-p[i].v); if(p[i].f<tm.x+1) { p[i].f=tm.x+1; p[i].w1=tm.y; }else if(p[i].f==tm.x+1)p[i].w1+=tm.y; } for(j=j-1;j>=l;j--)tr.clear(max_v-p[j].v); sort(p+l,p+r+1,cmps); cdq(mid+1,r); } void CDQ(int l,int r) { if(l==r)return ; int mid = (l+r)>>1; CDQ(mid+1,r); sort(p+l,p+mid+1,cmpH); sort(p+mid+1,p+r+1,cmpH); int i,j; for(i=l,j=mid+1;i<=mid;i++) { while(j<=r&&p[i].h>=p[j].h) { tr.up(p[j].v,p[j].g,p[j].w2); j++; } Pair tm = tr.down(p[i].v); if(p[i].g<tm.x+1) { p[i].g=tm.x+1; p[i].w2=tm.y; }else if(p[i].g==tm.x+1)p[i].w2+=tm.y; } for(j=j-1;j>mid;j--)tr.clear(p[j].v); sort(p+l,p+r+1,cmps); CDQ(l,mid); } int ans; int main() { n=rd(); for(int h,v,i=1;i<=n;i++) { h=rd(),v=rd(); ph[i].x=h,ph[i].y=i; pv[i].x=v,pv[i].y=i; p[i].s=i; } sort(ph+1,ph+1+n,cmp); for(int las=-1,k=0,i=1;i<=n;i++) { if(las!=ph[i].x) { las = ph[i].x; k++; } p[ph[i].y].h=k; } sort(pv+1,pv+1+n,cmp); for(int las=-1,k=0,i=1;i<=n;i++) { if(las!=pv[i].x) { las = pv[i].x; k++; max_v=k+1; } p[pv[i].y].v=k; } for(int i=1;i<=n;i++)p[i].f=1,p[i].w1=1.0; cdq(1,n); for(int i=1;i<=n;i++)ans=max(ans,p[i].f); printf("%d ",ans); for(int i=1;i<=n;i++)p[i].g=1,p[i].w2=1.0; CDQ(1,n); double sum = 0; for(int i=1;i<=n;i++) { if(p[i].f+p[i].g-1==ans) { sum+=p[i].w1*p[i].w2; } } sum/=(double)ans; for(int i=1;i<=n;i++) { if(p[i].f+p[i].g-1==ans) { printf("%.5lf ",p[i].w1*p[i].w2/sum); }else { printf("0.00000 "); } } printf(" "); return 0; }