【BZOJ2244】[SDOI2011]拦截导弹（CDQ分治）

时间：2021-02-18 08:05:44

【BZOJ2244】[SDOI2011]拦截导弹（CDQ分治）

题面

BZOJ

洛谷

题解

不难发现这就是一个三维偏序+\(LIS\)这样一个\(dp\)。

那么第一问很好求，直接\(CDQ\)分治之后\(dp\)就好了。

那么第二问呢？首先如果记一个方案数，显然就可以在转移的时候求出以每个点开头/结尾的\(LIS\)个数，这样子在算的时候前后乘一下再除掉全部的\(LIS\)数就是答案了。

说起来好简单啊，码起来就不一样了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 50500

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n;

struct Node{int h,v,i;}p[MAX];

int lb(int x){return x&(-x);}

int c[MAX];double w[MAX];

void add(int x,int v,double W)

{

	while(x<=n)

	{

		if(v==c[x])w[x]+=W;

		else if(v>c[x])c[x]=v,w[x]=W;

		x+=lb(x);

	}

}

int Query(int x){int ret=0;while(x)ret=max(ret,c[x]),x-=lb(x);return ret;}

double Query(int x,int v){double ret=0;while(x)ret+=(c[x]==v)?w[x]:0,x-=lb(x);return ret;}

int f[2][MAX];double g[2][MAX];

void clear(int x){while(x<=n)c[x]=w[x]=0,x+=lb(x);}

bool cmph(Node a,Node b){return a.h>b.h;}

bool cmpv(Node a,Node b){return a.v>b.v;}

bool cmpi(Node a,Node b){return a.i<b.i;}

void CDQ(int l,int r,int type)

{

	if(l==r)return;

	sort(&p[l],&p[r+1],cmpi);

	if(type)reverse(&p[l],&p[r+1]);

	int mid=(l+r)>>1;

	CDQ(l,mid,type);

	sort(&p[l],&p[mid+1],cmph);

	sort(&p[mid+1],&p[r+1],cmph);

	for(int i=mid+1,j=l;i<=r;++i)

	{

		while(j<=mid&&p[j].h>=p[i].h)

			add(n+1-p[j].v,f[type][p[j].i],g[type][p[j].i]),++j;

		int d=Query(n+1-p[i].v)+1;

		if(d>f[type][p[i].i])f[type][p[i].i]=d,g[type][p[i].i]=Query(n+1-p[i].v,d-1);

		else if(d==f[type][p[i].i])g[type][p[i].i]+=Query(n+1-p[i].v,d-1);

	}

	for(int i=l;i<=mid;++i)clear(n+1-p[i].v);

	CDQ(mid+1,r,type);

}

int Sh[MAX],toth,Sv[MAX],totv;

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i].h=read(),p[i].v=read(),p[i].i=i;

	for(int i=1;i<=n;++i)Sh[++toth]=p[i].h;

	sort(&Sh[1],&Sh[toth+1]);toth=unique(&Sh[1],&Sh[toth+1])-Sh-1;

	for(int i=1;i<=n;++i)p[i].h=lower_bound(&Sh[1],&Sh[toth+1],p[i].h)-Sh;

	for(int i=1;i<=n;++i)Sv[++totv]=p[i].v;

	sort(&Sv[1],&Sv[totv+1]);totv=unique(&Sv[1],&Sv[totv+1])-Sv-1;

	for(int i=1;i<=n;++i)p[i].v=lower_bound(&Sv[1],&Sv[totv+1],p[i].v)-Sv;

	for(int i=1;i<=n;++i)f[0][i]=f[1][i]=g[0][i]=g[1][i]=1;

	CDQ(1,n,0);

	reverse(&p[1],&p[n+1]);

	for(int i=1;i<=n;++i)p[i].v=n-p[i].v+1,p[i].h=n-p[i].h+1;

	CDQ(1,n,1);

	int ans=0;double sum=0;

	for(int i=1;i<=n;++i)ans=max(ans,f[0][i]);

	for(int i=1;i<=n;++i)if(f[0][i]==ans)sum+=g[0][i];

	printf("%d\n",ans);

	for(int i=1;i<=n;++i)

		if(f[0][i]+f[1][i]-1!=ans)printf("0.000000 ");

		else printf("%.6lf ",g[0][i]*g[1][i]/sum);

	puts("");return 0;

}

相关文章