如果他仅仅只是求最长二维非升序列长度 那么就是一个cdq模板题 dp一下即可
但是这题不仅要求dp 还要求dp的方案个数
所以用线段树来维护 区间最大值和区间最大值的个数
初始化的话build一次更快 （当maxx[pos]==0时不继续递归即可）
f2 g2 为反向
那么当
f1[i]+f2[i]-1!=maxxans 显然该元素不在任何最长子序列中
否则的话 答案为 所在方案的个数/总的方案个数 g1[i]*g2[i]/sum
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ///////////////////////////////////// const int N=1e6+10; ll maxx[N<<2]; double t[N<<2]; int n,m,anss[N],f1[N],f2[N],xx[N],yy[N]; double g1[N],g2[N]; void build(int l,int r,int pos) { if(!maxx[pos])return ;//这条加速非常重要 maxx[pos]=t[pos]=0; if(l==r){maxx[pos]=t[pos]=0;return ;} int m=(l+r)>>1;maxx[pos]=t[pos]=0; build(l,m,pos<<1);build(m+1,r,pos<<1|1); } void up(int pos) { if(maxx[pos<<1]<maxx[pos<<1|1]) maxx[pos]=maxx[pos<<1|1],t[pos]=t[pos<<1|1]; else if(maxx[pos<<1]>maxx[pos<<1|1]) maxx[pos]=maxx[pos<<1],t[pos]=t[pos<<1]; else maxx[pos]=maxx[pos<<1],t[pos]=t[pos<<1]+t[pos<<1|1]; } void upnode(int x,int v,double v2,int l,int r,int pos) { if(l==r) { if(v==maxx[pos])t[pos]+=v2; else if(v>maxx[pos])maxx[pos]=v,t[pos]=v2; return ; } int m=(l+r)>>1; if(x<=m)upnode(x,v,v2,l,m,pos<<1); else upnode(x,v,v2,m+1,r,pos<<1|1); up(pos); } ll qmax(int L,int R,int l,int r,int pos) { if(L<=l&&r<=R)return maxx[pos]; ll ans=0;int m=(l+r)>>1; if(L<=m)ans=max(ans,qmax(L,R,l,m,pos<<1)); if(R>m)ans=max(ans,qmax(L,R,m+1,r,pos<<1|1)); return ans; } double qnum(int L,int R,ll v,int l,int r,int pos) { if(L<=l&&r<=R){if(maxx[pos]==v)return t[pos];return 0; } int m=(l+r)>>1;double ans=0; if(L<=m)ans+=qnum(L,R,v,l,m,pos<<1); if(R>m)ans+=qnum(L,R,v,m+1,r,pos<<1|1); return ans; } struct node{int x,y,id;}s[N],temp[N]; bool cmp(node a,node b){return a.x<b.x;} void cdq1(int l,int r) { if(l==r)return ;int mid=(l+r)>>1; cdq1(mid+1,r); rep(i,l,r)temp[i]=s[i]; sort(temp+l,temp+mid+1,cmp);sort(temp+mid+1,temp+r+1,cmp); int j=mid+1; build(1,n,1); rep(i,l,mid) { while(j<=r&&temp[j].x<=temp[i].x)upnode(temp[j].y,f1[temp[j].id],g1[temp[j].id],1,n,1),j++; double cn=0; ll t=qmax(1,temp[i].y,1,n,1); if(!t)continue; cn=qnum(1,temp[i].y,t,1,n,1); if(f1[temp[i].id]<t+1)f1[temp[i].id]=t+1,g1[temp[i].id]=0; if(f1[temp[i].id]==t+1)g1[temp[i].id]+=cn; } cdq1(l,mid); } void cdq2(int l,int r) { if(l==r)return ;int mid=(l+r)>>1; cdq2(l,mid); rep(i,l,r)temp[i]=s[i]; sort(temp+l,temp+mid+1,cmp);sort(temp+mid+1,temp+r+1,cmp); int j=mid; build(1,n,1); repp(i,r,mid+1) { while(j>=l&&temp[j].x>=temp[i].x)upnode(temp[j].y,f2[temp[j].id],g2[temp[j].id],1,n,1),j--; double cn=0; ll t=qmax(temp[i].y,n,1,n,1); if(!t)continue; cn=qnum(temp[i].y,n,t,1,n,1); if(f2[temp[i].id]<t+1)f2[temp[i].id]=t+1,g2[temp[i].id]=0; if(f2[temp[i].id]==t+1)g2[temp[i].id]+=cn; } cdq2(mid+1,r); } int main() { cin>>n; rep(i,1,n)scanf("%d%d",&s[i].x,&s[i].y),s[i].id=i,f1[i]=f2[i]=1,xx[i]=s[i].x,yy[i]=s[i].y,g1[i]=g2[i]=1; sort(xx+1,xx+1+n);sort(yy+1,yy+1+n); int nx=unique(xx+1,xx+1+n)-xx-1; int ny=unique(yy+1,yy+1+n)-yy-1; rep(i,1,n) s[i].x=lower_bound(xx+1,xx+1+nx,s[i].x)-xx, s[i].y=lower_bound(yy+1,yy+1+ny,s[i].y)-yy; cdq1(1,n); int maxxans=0; double sum=0; rep(i,1,n)maxxans=max(maxxans,f1[i]); cout<<maxxans<<endl; rep(i,1,n) if(f1[i]==maxxans)sum+=g1[i]; sort(s+1,s+1+n,[](node a,node b){return a.id<b.id;}); cdq2(1,n); rep(i,1,n) { if(f1[i]+f2[i]-1!=maxxans)printf("0.00000 "); else printf("%.5lf ",g1[i]*g2[i]/sum); } return 0; }