题目
做\(SDOI\)有种想评黑的感觉，果然还是太弱了
做法
独立写(调)代码三个小时祭
简化题目：求二维最长不上升子序列及每个点出现在最长不上升子序列概率
我们的限制条件：\(t_j<t_i,h_j \geqslant h_i,v_j\geqslant v_i\)，求长度随便套个\(cdq\)随便就做出来了嘛
毒瘤的出题人怎么可能这么简单就让我们切了这道题，那怎么求概率呢？
设\(L_i\)为以\(i\)结尾的最长长度(不包括\(i\))，那包含\(i\)的最长长度为\(L_i+1+R_i\)
设\(Lnum_i\)为以\(i\)结尾的最长长度(不包括\(i\))的个数，
那包含\(i\)的最长长度为\(L_i+1+R_i\)的总个数为：\(Lnum_i×Rnum_i\)。特殊地，长度为\(0\)是，个数为\(1\)
那总个数呢？\(\sum\limits_{i=1}^n(Lnum_i×Rnum_i)\)然后发现全\(WA\)了，我们重复统计，因为同一子序列会在所以点里算一遍
正确的做法，枚举每一个右端点，即\(R_i==0\)&&\(L_i+1==ans\)，满足这个条件再统计方案就不会重复计算了
抱着能shi做shi出kan来的心态打了一遍冗长的代码，发现只有7分，想*的心都有了，然后造出一组数据拍掉了
6
4 25
4 30
4 35
4 40
4 45
4 50
因为长度为\(0\)时，查询后相加方案数会变成\(2\)，所以在每次查询后暴力加个判断改回\(1\)，然后惊奇的发现\(85\)分了
剩下是由于long long爆了，那我们就把方案数换double，撒花撒花！！
My complete code
非常无耻地压了点行
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<ctime>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const LL maxn=1e5;
inline LL Read(){
LL x(0),f(1);char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
LL n,tot1,tot2;
LL tmp1[maxn],tmp2[maxn],tree1[maxn],tree2[maxn];
double num1[maxn],num2[maxn];
struct Qy{
double num;LL val;
}L[maxn],R[maxn];
inline LL Lowbit(LL x){return x&(-x);}
inline void Cmax(LL x,LL val,double ret){
if(tree2[x]==val)
num2[x]+=ret;
else if(tree2[x]<val)
tree2[x]=val,num2[x]=ret;
for(;x<=tot2;x+=Lowbit(x))
if(tree1[x]==val)
num1[x]+=ret;
else if(tree1[x]<val)
tree1[x]=val,num1[x]=ret;
}
inline Qy Query(LL l,LL r){
LL val(0);double ret(1.0);
while(l<=r){
LL r1=r-Lowbit(r);
if(r1+1>=l){
if(tree1[r]!=0)
if(tree1[r]==val)
ret+=num1[r];
else if(val<tree1[r])
val=tree1[r],ret=num1[r];
r=r1;
}else{
if(tree2[r]!=0)
if(tree2[r]==val)
ret+=num2[r];
else if(val<tree2[r])
val=tree2[r],ret=num2[r];
--r;
}
}return (Qy){ret,val};
}
inline void Clear(LL x){
tree2[x]=0,num2[x]=0;
for(;x<=tot2;x+=Lowbit(x))
tree1[x]=0,num1[x]=0;
}
struct node{
LL t,h,v,id;
}a[maxn];
inline bool cmp0(node x,node y){return x.t<y.t; }
inline bool cmp1(node x,node y){return x.h>y.h; }
void Cdq1(LL l,LL r){
if(l==r) return;
LL mid(l+r>>1),t1(l-1);
Cdq1(l,mid);
sort(a+l,a+mid+1,cmp1),sort(a+mid+1,a+r+1,cmp1);
for(LL i=mid+1;i<=r;++i){
while(t1<mid&&a[t1+1].h>=a[i].h)
++t1,Cmax(a[t1].v,L[a[t1].id].val+1,L[a[t1].id].num);
Qy tmp=Query(a[i].v,tot2);
if(tmp.val==L[a[i].id].val)
L[a[i].id].num+=tmp.num;
else if(tmp.val>L[a[i].id].val)
L[a[i].id]=tmp;
if(L[a[i].id].val==0)
L[a[i].id].num=1;
}
for(LL i=l;i<=t1;++i)
Clear(a[i].v);
sort(a+l,a+r+1,cmp0);
Cdq1(mid+1,r);
}
inline bool cmp2(node x,node y){return x.t>y.t; }
inline bool cmp3(node x,node y){return x.h<y.h; }
void Cdq2(LL l,LL r){
if(l==r) return;
LL mid(l+r>>1),t1(l-1);
Cdq2(l,mid);
sort(a+l,a+mid+1,cmp3),sort(a+mid+1,a+r+1,cmp3);
for(LL i=mid+1;i<=r;++i){
while(t1<mid&&a[t1+1].h<=a[i].h)
++t1,Cmax(a[t1].v,R[a[t1].id].val+1,R[a[t1].id].num);
Qy tmp=Query(1,a[i].v);
if(tmp.val==R[a[i].id].val)
R[a[i].id].num+=tmp.num;
else if(tmp.val>R[a[i].id].val)
R[a[i].id]=tmp;
if(R[a[i].id].val==0)
R[a[i].id].num=1;
}
for(LL i=l;i<=t1;++i)
Clear(a[i].v);
sort(a+l,a+r+1,cmp2);
Cdq2(mid+1,r);
}
int main(){
n=Read();
for(LL i=1;i<=n;++i)
a[i].h=tmp1[i]=Read(),a[i].v=tmp2[i]=Read(),a[i].t=i;
sort(tmp1+1,tmp1+1+n),sort(tmp2+1,tmp2+1+n);
tot1=unique(tmp1+1,tmp1+1+n)-1-tmp1,tot2=unique(tmp2+1,tmp2+1+n)-1-tmp2;
for(LL i=1;i<=n;++i)
a[i].h=lower_bound(tmp1+1,tmp1+1+tot1,a[i].h)-tmp1,
a[i].v=lower_bound(tmp2+1,tmp2+1+tot2,a[i].v)-tmp2,
a[i].id=i;
L[1].num=R[n].num=1.0;
Cdq1(1,n);
sort(a+1,a+1+n,cmp2);
Cdq2(1,n);
LL ans(0); double num(0);
for(LL i=1;i<=n;++i)
ans=max(ans,L[i].val+1+R[i].val);
for(LL i=1;i<=n;++i)
if(L[i].val+1==ans)
num+=L[i].num;
printf("%lld\n",ans);
for(LL i=1;i<=n;++i)
if(L[i].val+1+R[i].val==ans)
printf("%.5lf ",(double)L[i].num*R[i].num/num);
else
printf("0.00000 ");
return 0;
}/*
*/