bzoj2244 [SDOI2011]攔截飛彈 cdq分治

這個題看起來是二維偏序，但實際上是三維偏序（高度、速度、順序）

是以就用順序減掉一維，cdq減掉一維，用資料結構減掉一維，

然後求每個點的機率就等于 經過他的方案數/方案總數

然後首先要知道lis的答案，用cdq分治轉移一遍即可出解，但由于要算方案總數，是以需要記錄 到一個點 dp值最大時的方案數

但經過他的方案數不隻有到一個點的方案數，還有他到終點的方案數，

這時有一個比較顯然的結論，對于最長的lis上的每一個點， 存在的充要條件是 前面比他小的點的個數+後面比他大的點的個數=答案-1

對于方案就是用乘法原理，兩個方案乘起來即可

比較難寫，注意可能會爆int，需要用double

碼：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define zuo o<<1,l,mid
#define you o<<1|1,mid+1,r
#define N 100005
int ql[N<<2],maxx[N<<2],a,b,op,c,n,lin[N],ans,zz;
double cnt,sz[N<<2],d;
struct la
{
	int a,b,c,f,g;
	double sz,sz2;
}D[50005];
void up(int o)
{
	int ll=o<<1,rr=o<<1|1;
if(maxx[ll]==maxx[rr])
{
	sz[o]=sz[ll]+sz[rr];
}else
{
if(maxx[ll]<maxx[rr])swap(ll,rr);
maxx[o]=maxx[ll];
sz[o]=sz[ll];
}
}
void push(int o)
{
	int ll=o<<1,rr=o<<1|1;
if(ql[o])
{
	ql[ll]=ql[rr]=1;
	maxx[ll]=0;
	maxx[rr]=0;	
	sz[ll]=0;
	sz[rr]=0;
	ql[o]=0;
}
}
void gai(int o,int l,int r)
{
	if(a<=l&&r<=b)
	{
		if(op==0)
		{
			if(c==maxx[o])sz[o]+=d;
              if(c>maxx[o])sz[o]=d,maxx[o]=c;
					
		}else
		{
if(c==maxx[o])d+=sz[o];
if(c<maxx[o])c=maxx[o],d=sz[o];			
		}
		return ;
	}
	push(o);
	int mid=(l+r)>>1;
	if(a<=mid)gai(zuo);
	if(b>mid)gai(you);
	up(o);
}
bool cmpa(la A,la B)
{
	return A.a>B.a;
}
bool cmpaa(la A,la B)
{
	return A.a<B.a;
}
bool cmpb(la A,la B)
{
	return A.b<B.b;
}
bool cmpc(la A,la B)
{
	return A.c<B.c;
}
bool cmpcc(la A,la B)
{
	return A.c>B.c;
}
void cdq(int l,int r)
{
	int mid=(l+r)>>1,i;
	if(l==r)return;
	cdq(l,mid);
sort(D+l,D+mid+1,cmpa);
sort(D+mid+1,D+r+1,cmpa);
zz=l;
	for(i=mid+1;i<=r;i++)
	{
		while(D[zz].a>=D[i].a&&zz<=mid)
		{
	a=b=D[zz].b;
    c=D[zz].f;
	d=D[zz].sz;
	op=0;
    gai(1,1,n);zz++;
		}
		a=D[i].b;b=n;
		c=d=0;op=1;
		if(a<=b)gai(1,1,n);
		if(D[i].f==c+1)D[i].sz+=d;
		else if(D[i].f<c+1)
		{
			D[i].f=c+1;
			D[i].sz=d;
		}	
	}
	//清零
	maxx[1]=0;	sz[1]=0;
	ql[1]=1;
	sort(D+mid+1,D+r+1,cmpc);
	cdq(mid+1,r);
}
void cdq2(int l,int r)
{
	int mid=(l+r)>>1,i;
	if(l==r)return;
	cdq2(l,mid);
sort(D+l,D+mid+1,cmpaa);
sort(D+mid+1,D+r+1,cmpaa);
zz=l;
	for(i=mid+1;i<=r;i++)
	{
		while(zz<=mid&&D[zz].a<=D[i].a)
		{
				a=b=D[zz].b;
    c=D[zz].g;d=D[zz].sz;
	op=0;
    gai(1,1,n);zz++;
		}
		a=1;b=D[i].b;
		c=d=0;op=1;
		if(a<=b)gai(1,1,n);
	if(D[i].g==c+1)D[i].sz+=d;
	if(D[i].g<c+1)
	{
		D[i].g=c+1;
		D[i].sz=d;
	}
	}
	//清零
	maxx[1]=0;
	sz[1]=0;
	ql[1]=1;
	sort(D+mid+1,D+r+1,cmpcc);
	cdq2(mid+1,r);
}
int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	scanf("%d%d",&D[i].a,&D[i].b),D[i].c=i;
	sort(D+1,D+1+n,cmpb);
	for(i=1;i<=n;i++)
	{D[i].f=D[i].g=D[i].sz=1;
		if(D[i].b==D[i-1].b)lin[i]=lin[i-1];
		else lin[i]=i;		
	}
	for(i=1;i<=n;i++)
	D[i].b=lin[i];
	sort(D+1,D+1+n,cmpc);
	cdq(1,n);
	for(i=1;i<=n;i++)
	ans=max(ans,D[i].f),D[i].sz2=D[i].sz,D[i].sz=1;
printf("%d\n",ans);
for(i=1;i<=n;i++)
{
	if(D[i].f==ans)cnt+=D[i].sz2;
}
sort(D+1,D+1+n,cmpcc);
	cdq2(1,n);
sort(D+1,D+1+n,cmpc);
for(i=1;i<=n;i++)
{
if(D[i].g+D[i].f==ans+1)printf("%.5lf ",(D[i].sz*D[i].sz2)/(cnt));
else printf("0.00000 ");
}	
}