BZOJ2244 攔截導彈

此題最早看到是在我還什麼都不會的去年的暑期集訓，是V8講的DP專題，我當時還跑去問這概率怎麼做。這道題要求的是二維最長不上升子序列，加上位置一維就成了三維偏序問題，也就是套用CDQ分治，對位置排序，然後對一維分治，對剩下的一維樹狀數組，類似的問題用樹狀數組套平衡樹也能解決，但似乎常數很大。然後這題的第一個關鍵就是在做CDQ的時候先做CDQ（l,mid）的區間，然後去計算左邊對右邊的影響，最後去計算CDQ(mid+1,r)，昨晚看別人博客中說這是顯然的，當時我就懵逼了，於是這題今天上課看了很久。發現的確要這麼做的，因為其實你是在維護第三維樹狀數組的時候去做了這個DP的過程，當計算以該點為結尾的最長不上升子序列時，你當然應該先做左區間，然後就可以去更新一下相對右邊這些點的值，然後就再去做CDQ的右區間。具體是分別維護區間的最長不上升子序列的長度，以及出現的次數。做法是這樣的，首先對左右兩邊分別按照第二維從小到大排序，將左邊的所有的第二維大於右邊的點全部加入樹狀數組，更新第三維，要註意更新和查詢的方向正好是反過來的，因為你要查的是大於右邊某個值的最長不上升子序列的長度，然後更新一下dp數組，也就是代碼中的f[0]數組。然後再把整個序列反過來做一遍CDQ，求以某個點為開始的最長不上升子序列。

加一個學習的鏈接：https://www.cnblogs.com/liu-runda/p/6416195.html  

#include<bits/stdc++.h>
#define ll long double
#define pb push_back
#define _mp make_pair
const int maxn=1e5+7;
const int mod=1e9+7;
using namespace std;
int n;
int h[2][maxn],v[2][maxn];
int iq[maxn],hq[maxn],vq[maxn];
int f[2][maxn];
ll g[2][maxn];
int MAX[maxn];
ll CNT[maxn];
void add1(int x,int w,ll cnt)
{
	while(x>0)
	{
		if(MAX[x]<w)
		{
			MAX[x]=w;CNT[x]=cnt;
		}
		else if(MAX[x]==w)CNT[x]+=cnt;
		x-=x&-x;
	}
}
void add2(int x,int w,ll cnt)
{
	while(x<maxn)
	{
		if(MAX[x]<w)
		{
			MAX[x]=w;CNT[x]=cnt;
		}
		else if(MAX[x]==w)CNT[x]+=cnt;
		x+=x&-x;
	}
}
int query1(int x)
{
	int ans=0;
	while(x<maxn)
	{
		if(MAX[x]>ans)ans=MAX[x];
		x+=x&-x;
	}
	return ans;
}
int query2(int x)
{
	int ans=0;
	while(x>0)
	{
		if(MAX[x]>ans)ans=MAX[x];
		x-=x&-x;
	}
	return ans;
}
ll query_cnt(int x,int val)
{
	ll ans=0;
	while(x<maxn)
	{
		if(MAX[x]==val)ans+=CNT[x];
		x+=x&-x;
	}
	return ans;
}
ll query_cnt2(int x,int val)
{
	ll ans=0;
	while(x>0)
	{
		if(MAX[x]==val)ans+=CNT[x];
		x-=x&-x;
	}
	return ans;
}
bool cmp1(const int& a,const int& b)
{
	return h[0][a]<h[0][b];
}
bool cmp2(const int& a,const int& b)
{
	return v[0][a]<v[0][b];
}
bool cmp3(const int& a,const int& b)
{
	return h[1][a]<h[1][b];
}
void del1(int x)
{
	while(x>0)
	{
		MAX[x]=CNT[x]=0;
		x-=x&-x;
	}
}
void del2(int x)
{
	while(x<maxn)
	{
		MAX[x]=CNT[x]=0;
		x+=x&-x;
	}
}
void cdq1(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq1(l,mid);
	for(int i=l;i<=r;i++)iq[i]=i;
	sort(iq+l,iq+mid+1,cmp1);
	sort(iq+mid+1,iq+r+1,cmp1);
	int pp=mid;
	for(int i=r;i>mid;i--)
	{
		while(pp>=l&&h[0][iq[pp]]>=h[0][iq[i]])
		{
			add1(v[0][iq[pp]],f[0][iq[pp]],g[0][iq[pp]]);
			pp--;
		}
		int tmp=query1(v[0][iq[i]]);
		if(tmp+1>f[0][iq[i]])
		{
			f[0][iq[i]]=tmp+1;g[0][iq[i]]=query_cnt(v[0][iq[i]],tmp);
		}
		else if(tmp+1==f[0][iq[i]])
		{
			g[0][iq[i]]+=query_cnt(v[0][iq[i]],tmp);
		}
	}
	for(int i=mid;i>pp;i--)
	{
		del1(v[0][iq[i]]);
	}
	cdq1(mid+1,r);
}
void cdq2(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq2(l,mid);
	for(int i=l;i<=r;i++)iq[i]=i;
	sort(iq+l,iq+mid+1,cmp3);
	sort(iq+mid+1,iq+r+1,cmp3);
	int pp=l;
	for(int i=mid+1;i<=r;i++)
	{
		while(pp<=mid&&h[1][iq[pp]]<=h[1][iq[i]])
		{
			add2(v[1][iq[pp]],f[1][iq[pp]],g[1][iq[pp]]);
			pp++;
		}
		int tmp=query2(v[1][iq[i]]);
		if(tmp+1>f[1][iq[i]])
		{
			f[1][iq[i]]=tmp+1;g[1][iq[i]]=query_cnt2(v[1][iq[i]],tmp);
		}
		else if(tmp+1==f[1][iq[i]])
		{
			g[1][iq[i]]+=query_cnt2(v[1][iq[i]],tmp);
		}
	}
	for(int i=l;i<pp;i++)
	{
		del2(v[1][iq[i]]);
	}
	cdq2(mid+1,r);
}
int main()
{	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&h[0][i],&v[0][i]);
		iq[i]=i;
	}
//	cout<<222<<endl;
	sort(iq+1,iq+1+n,cmp1);
	int tot=0,las=-1;
	for(int i=1;i<=n;i++)
	{
		if(las!=h[0][iq[i]])
		{
			las=h[0][iq[i]];
			++tot;
		}
		h[0][iq[i]]=tot;
	}
	tot=0;las=-1;
	for(int i=1;i<=n;i++) iq[i]=i;
	sort(iq+1,iq+1+n,cmp2);
	for(int i=1;i<=n;i++)
	{
		if(las!=v[0][iq[i]])
		{
			las=v[0][iq[i]];
			++tot;
		}v[0][iq[i]]=tot;
	}
	for(int i=1;i<=n;i++)
	{
		h[1][i]=h[0][n+1-i];
		v[1][i]=v[0][n+1-i];
	}
	for(int i=1;i<=n;i++)
	{
		iq[i]=i;
		f[0][i]=f[1][i]=g[0][i]=g[1][i]=1;
	}
//	cout<<222<<endl;
	cdq1(1,n);cdq2(1,n);
//	cout<<222<<endl;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(f[0][i]>ans)ans=f[0][i];
	}
	printf("%d\n",ans);
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		if(f[0][i]==ans)sum+=g[0][i];
	}
	//cout<<sum<<endl;
	for(int i=1;i<=n;i++)
	{
	//	cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl;
		if(f[0][i]+f[1][n-i+1]!=ans+1)printf("%.8f ",0.0);
		else printf("%.8f ",double(g[0][i]*g[1][n-i+1]/(sum)));
		//cout<<endl;
	//	cout<<222<<endl;
	}
//	}
//	for(int i=1;i<=n;i++)	cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl;
	
}