题解 P2487 【[SDOI2011]拦截导弹】

· · 题解

假 long long 害人！一定要开double！

这道题的话首先你要注意到一个隐藏条件，所有导弹按照题目给出的顺序按时间发射……，所以我们现在就发现一个导弹有3个属性(h,v,t)，我们似乎可以dp？

然后会发现我们的dp方程大概长这样，令dp[i]表示以i为结尾的最长上升子序列，那么我们会发现

dp[i]=max(dp[j])+1满足i>j,hi<hj,vi<vj

所以我们就需要同时满足以上3个限制才可以dp，但是反过来，如果我们满足了这3个条件，并且满足涉及到的所有状态已经是准(值不会再变化)的了，我们就可以随便dp了

如果是正常的暴力的话，每个dp[i]只会被计算一次，更新对象是所有的偏序点

更新是O(n)的，但更新一次，非常的不平衡，因此我们要采取一些有趣的操作使得这两个操作都变成log级的，所以我们要用

CDQ分治

这里的cdq分治是处理多维元素的双排型分治，不是处理操作-询问序列的分治

(但是写法都很像所以一般不做区分)

思路和线段树十分相似，我们考虑cdq分治的实际操作过程，大家一般都会告诉你

1.分治左侧

2.考虑左侧对右侧的影响

3.分治右侧

简直是玄学啊……，或者说，cdq分治为什么要这么写？

不如我们考虑一个点在整个算法中会发生什么

我们发现把导弹按时间从大到小排序之后，可以更新dp[i]的点一定是一个连续的区间，具体来讲，是一个前缀，而这个前缀，是可以被拆分为log个2^i的整区间的(下面的“左侧”，“右侧”，“区间”的概念都是指按i排好序的区间)

我们假设这个点在右半部分，我们第一次分治完左侧之后假设我们使用了一些奥妙重重的方法使得左侧点的dp值全部变成了准的值，那么dp值要准的条件就被满足了。

此时我们发现左侧的i值都大于右侧的i值，也就是说，如果只考虑左侧的状态去更新右边的状态的话i的限制已经不存在了，因此我们现在可以对左右的状态进行一些乱搞。

比如排序，我们将左边和右边的序列按H排序，此时我们开始考虑左侧对右侧的更新限制

我们此时维护两个指针(数组下标?)，假设左侧的指针是p，右侧是i，我们如果要更新i的话，可以将指针p向右移，直到hp是最后一个小于等于hi的数，此时我们会发现从左侧起始点到p的这一段区间来讲，它们的h值都是小于hi的，我们会发现此时的h这一维的限制已经不存在了，现在我们要解决最后一维的问题，尴尬的发现我们已经不可以再乱动这个序列了

不过我们有数据结构~，离散化v之后按v插到树状数组里，发现v<vi这个条件是一个前缀限制条件，因此我们可以直接查前缀最大值~

至此折腾来折腾去，我们终于更新了一个点，而且，这个点还没被dp全…… 但是我们发现这个点最前面的区间已经被更新了，同时，将来有可能去更新i的点也全部被更新了，而且我们会发现每次都是采取分治左-更新-分治右的策略

非常像二叉树的中序遍历，而我们知道二叉树的中序遍历是有序的，因此，各个点变准的时间是和原来按时间排序之后暴力dp的时间是一样的。并且，每次更新完之后总是会有一个点的值变准，就是右侧区间的最左点，已经是准的了，因为没有点可以更新它了

另外我们会发现这个点i接下来还会再分治右的过程中再次被更新log次，直到他成为某个右侧区间的最左点，此时他就准了，而更新它的log个区间，刚好是按线段树方式剖分出来的log个区间。因此开头那个奥妙重重的方式，不过是递归定义而已，一旦这个点成为了右侧最左点，就会变准，成为接下来的左侧区间。

分治法和dp的滚动数组优化非常像，都是不改变时间复杂度的空间优化，通过时间上生成一棵分治树，可以看出来，cdq分治的过程相当于线段树上跑一遍中序遍历，代替了平常树套树的外层树，当然也减少了代码难度，比如这道题写起来就贼短

关于概率，显然每个点的概率=包含他的方案数/总方案数

(以下的前边和后边均指按时间排好序的导弹序列)

另一个显然的事实是，包含它的方案数=前边最长序列的方案数*后边最长序列的方案数

还有一个显然的事实是，它的长度=前边最长序列的长度+后边最长序列的长度-1

dp方案数的时候，如果max变了，就要重新赋值，如果相等的话，就要相加

总方案数的话，我们发现所有的点前方案*后方案再相加的话会重复统计，所以我们们只是枚举结尾点(或开头点)这样就可以了

所以我们跑两边cdq一遍正着跑一边倒着跑，最后利用两边的结果算出答案即可 (应该知道只有最大值才能进入算概率这个环节吧……否则直接输出0就好了)

坑

这里我突发奇想，想要把小于号全部改成大于号跑第二遍cdq这样就只用写一个cdq了……

所以我机(zhi)智(zhang)的在cmp中加了这么一句

return (a.v<b.v)^tr;

然后把tr改成1就可以小于变大于了，代码什么的完全不用改

但是，如果你足够熟练的话，会发现小于号取反，是大于等于，不是大于！

然后我们发现，大于等于/小于等于这个玩意，传到sort里是会挂掉的……会re的

( 真是令人智熄的操作)

解决方案：换stable_sort或者老老实实写一个根据tr判定的cmp

另一个坑就是不要开longlong，开了long long还是会乘爆/加爆，所以我们要开double，因为double的本质是科学计数法，当数变得过大时会牺牲精度来换取值域大小(比如表示一个233*10^1此时你加1是不会有反应的)所以乘爆什么的不存在的……

上代码~(其实非常短233)

#include<cstdio>
#include<algorithm>
using namespace std;
typedef double db;const int N=1e6+10;
struct data{int h;int v;int p;int ma;db ca;}a[2][N];int n;bool tr;//不要取反！ 
inline bool cmp1(const data& a,const data& b){if(tr)return a.h>b.h;else return a.h<b.h;}
inline bool cmp2(const data& a,const data& b){if(tr)return a.v>b.v;else return a.v<b.v;}
inline bool cmp3(const data& a,const data& b){if(tr)return a.p<b.p;else return a.p>b.p;}
inline bool cmp4(const data& a,const data& b){return a.v==b.v;}
struct treearray//树状数组，记得再维护一个方案数 
{
    int ma[2*N];db ca[2*N];
    inline void c(int x,int t,db c)//修改 
    {for(;x<=n;x+=x&(-x)){if(ma[x]==t){ca[x]+=c;}else if(ma[x]<t){ca[x]=c;ma[x]=t;}}}
    inline void d(int x){for(;x<=n;x+=x&(-x)){ma[x]=0;ca[x]=0;}}//删除 
    inline void q(int x,int& m,db& c)//询问(其实这里不是故意叫cdq的) 
    {for(;x>0;x-=x&(-x)){if(ma[x]==m){c+=ca[x];}else if(m<ma[x]){c=ca[x];m=ma[x];}}}
}ta;int rk[2][N];
inline void solve(int l,int r,int t)//分治 
{
    if(r-l==1){return;}int mid=(l+r)/2;
    solve(l,mid,t);sort(a[t]+mid+1,a[t]+r+1,cmp1);int p=l+1;
    for(int i=mid+1;i<=r;i++)//维护双指针 ，记得判相等 
    {
        for(;(cmp1(a[t][p],a[t][i])||a[t][p].h==a[t][i].h)&&p<=mid;p++)
        {ta.c(a[t][p].v,a[t][p].ma,a[t][p].ca);}db c=0;int m=0;ta.q(a[t][i].v,m,c);
        if(a[t][i].ma<m+1){a[t][i].ma=m+1;a[t][i].ca=c;}else if(a[t][i].ma==m+1){a[t][i].ca+=c;}
    }for(int i=l+1;i<=mid;i++){ta.d(a[t][i].v);}//记得回撤 
    sort(a[t]+mid,a[t]+r+1,cmp3);solve(mid,r,t);//这里注意，大力sorth后要sort回来，你后边还没解决呢 
    sort(a[t]+l+1,a[t]+r+1,cmp1);//最后按h排好序 
}
inline void ih(int t)//这里是离散化 
{
    sort(a[t]+1,a[t]+n+1,cmp2);rk[t][1]=1;//这样两次树状数组都可以只查前缀了 
    for(int i=2;i<=n;i++){rk[t][i]=(cmp4(a[t][i],a[t][i-1]))?rk[t][i-1]:i;}
    for(int i=1;i<=n;i++){a[t][i].v=rk[t][i];}sort(a[t]+1,a[t]+n+1,cmp3);
    for(int i=1;i<=n;i++){a[t][i].ma=1;a[t][i].ca=1;}//赋dp初值 
}int len;db ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[0][i].h,&a[0][i].v);a[0][i].p=i;
        a[1][i].h=a[0][i].h;a[1][i].v=a[0][i].v;a[1][i].p=i;
    }ih(0);solve(0,n,0);tr=1;ih(1);solve(0,n,1);tr=1;//两边cdq 
    sort(a[0]+1,a[0]+n+1,cmp3);sort(a[1]+1,a[1]+n+1,cmp3);//统计答案要sort回来 
    for(int i=1;i<=n;i++){len=max(len,a[0][i].ma);}printf("%d\n",len);
    for(int i=1;i<=n;i++){if(a[0][i].ma==len){ans+=a[0][i].ca;}}
    for(int i=1;i<=n;i++)//然后强行计算期望就好了 
    {
        if(a[0][i].ma+a[1][i].ma-1==len){printf("%.5lf ",(a[0][i].ca*a[1][i].ca)/ans);}
        else {printf("0.00000 ");}
    }return 0;//拜拜程序~ 
}