题目大意：给定一个序列，每个元素是一个二元组，等概率选择一LIS，求LIS长度以及每个元素被选中的概率
第一问CDQ分治裸上
第二问用每个元素所在的LIS个数/总LIS个数就是答案
每个元素所在的LIS自己必选，然后统计前面的方案数和后面的方案数
以前面的方案数为例，令f[x]为以x结尾的LIS长度，那么有DP方程：
g[i]=Σg[j] (f[j]+1=f[i],j<i,a[j].x<a[i].x,a[j].y<a[i].y)
将所有元素按f值排序，分层DP，，每层DP是一个三维偏序，上CDQ分治再搞搞就好了
(我偷懒写了二维树状数组QAQ)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 50500using namespace std;typedef double ld;int n,ans,tot;int f[M];ld g[M],h[M],total;struct abcd{int x,y;}*a[M],*_a[M],mempool[M];bool Compare(abcd *a1,abcd *a2){if( a1->x != a2->x )return a1->x < a2->x ;return a1->y < a2->y ;}bool _Compare(int x,int y){if( f[x] != f[y] )return f[x] < f[y] ;return x < y ;}void Discretization(){static pair<int,int*> b[M];int i;for(i=1;i<=n;i++)b[i]=make_pair(-a[i]->x,&a[i]->x);sort(b+1,b+n+1);for(tot=0,i=1;i<=n;i++){if(i==1||b[i].first!=b[i-1].first)++tot;*b[i].second=tot;}for(i=1;i<=n;i++)b[i]=make_pair(-a[i]->y,&a[i]->y);sort(b+1,b+n+1);for(tot=0,i=1;i<=n;i++){if(i==1||b[i].first!=b[i-1].first)++tot;*b[i].second=tot;}}namespace BIT{int c[M],tim[M],T;void Initialize(){++T;}void Update(int x,int y){for(;x<=n;x+=x&-x){if(tim[x]!=T)tim[x]=T,c[x]=0;c[x]=max(c[x],y);}}int Get_Ans(int x){int re=0;for(;x;x-=x&-x)if(tim[x]==T)re=max(re,c[x]);return re;}}void CDQ_Divide_And_Conquer(int l,int r){using namespace BIT;int i,j,mid=l+r>>1;if(l==r){f[mid]++;ans=max(ans,f[mid]);return ;}int l1=l,l2=mid+1;for(i=l;i<=r;i++)if(a[i]-mempool<=mid)_a[l1++]=a[i];else_a[l2++]=a[i];memcpy(a+l,_a+l,sizeof(a[0])*(r-l+1));CDQ_Divide_And_Conquer(l,mid);Initialize();for(j=l,i=mid+1;i<=r;i++){for(;j<=mid&&a[j]->x<=a[i]->x;j++)Update(a[j]->y,f[a[j]-mempool]);f[a[i]-mempool]=max(f[a[i]-mempool],Get_Ans(a[i]->y));}CDQ_Divide_And_Conquer(mid+1,r);l1=l;l2=mid+1;for(i=l;i<=r;i++)if( l2>r || l1<=mid && Compare(a[l1],a[l2]) )_a[i]=a[l1++];else_a[i]=a[l2++];memcpy(a+l,_a+l,sizeof(a[0])*(r-l+1));}namespace Bidimensional_BIT{namespace Hash_Table{struct List{int x,y;ld val;List *next;List() {}List(int _,int __,List *___):x(_),y(__),val(0),next(___) {}}mempool[12000000],*C=mempool,*head[1031][1301];int tim[1031][1301],T;void Initialize(){C=mempool;++T;}ld& Hash(int x,int y){int pos1=x%1031,pos2=y%1301;List *temp;if(tim[pos1][pos2]!=T)tim[pos1][pos2]=T,head[pos1][pos2]=0;for(temp=head[pos1][pos2];temp;temp=temp->next)if(temp->x==x&&temp->y==y)return temp->val;return (head[pos1][pos2]=new List(x,y,head[pos1][pos2]))->val;}ld Get_Hash(int x,int y){int pos1=x%1031,pos2=y%1301;List *temp;if(tim[pos1][pos2]!=T)tim[pos1][pos2]=T,head[pos1][pos2]=0;for(temp=head[pos1][pos2];temp;temp=temp->next)if(temp->x==x&&temp->y==y)return temp->val;return 0;}}using namespace Hash_Table;void Update(int x,int y,ld val,int flag){int i,j;for(i=x;i&&i<=n;i+=flag*(i&-i))for(j=y;j&&j<=n;j+=flag*(j&-j))Hash(i,j)+=val;}ld Get_Ans(int x,int y,int flag){ld re=0;int i,j;for(i=x;i&&i<=n;i+=flag*(i&-i))for(j=y;j&&j<=n;j+=flag*(j&-j))re+=Get_Hash(i,j);return re;}}int main(){//freopen("3756.in","r",stdin);//freopen("3756.out","w",stdout);int i,j;cin>>n;for(i=1;i<=n;i++){scanf("%d%d",&mempool[i].x,&mempool[i].y);a[i]=&mempool[i];}Discretization();sort(a+1,a+n+1,Compare);CDQ_Divide_And_Conquer(1,n);cout<<ans<<endl;static int a[M];for(i=1;i<=n;i++)a[i]=i;sort(a+1,a+n+1,_Compare);for(i=1;i<=n&&f[a[i]]==1;i++)g[a[i]]=1;for(j=1;i<=n;i++){if(f[a[i]]!=f[a[i-1]]){for(;f[a[j]]+1!=f[a[i]];j++);Bidimensional_BIT::Initialize();}for(;a[j]<a[i]&&f[a[j]]==f[a[i]]-1;j++)Bidimensional_BIT::Update(mempool[a[j]].x,mempool[a[j]].y,g[a[j]],1);g[a[i]]=Bidimensional_BIT::Get_Ans(mempool[a[i]].x,mempool[a[i]].y,-1);}for(i=n;i&&f[a[i]]==ans;i–)h[a[i]]=1;for(j=n;i;i–){if(f[a[i]]!=f[a[i+1]]){for(;f[a[j]]-1!=f[a[i]];j–);Bidimensional_BIT::Initialize();}for(;a[j]>a[i]&&f[a[j]]==f[a[i]]+1;j–)Bidimensional_BIT::Update(mempool[a[j]].x,mempool[a[j]].y,h[a[j]],-1);h[a[i]]=Bidimensional_BIT::Get_Ans(mempool[a[i]].x,mempool[a[i]].y,1);}for(i=1;i<=n&&f[a[i]]==1;i++)total+=h[a[i]];for(i=1;i<=n;i++)printf("%.10lf%c",(double)(g[i]*h[i]/total),i==n?'\n':' ');return 0;}
烦恼忧愁不用追，吃点好的别嫌贵，
