P2487 [SDOI2011]拦截导弹

MCAdam · 2020-04-03 13:55:41 · 题解

题目

普及组题目

这道题让我重新认识了CDQ计算顺序的问题

第一问求的就是二维的最长不上升子序列。设f1_i表示以i结尾的最长不上升子序列，g1_i表示以i结尾的最长不上升子序列的方案数。那么转移为

把DP的过程转成离线，那么就是一个三维偏序问题。记三元组(pos,h,v)，pos是位置（也可以理解为时间），用CDQ解决就可以了。注意这里的数据结构支持：修改单点的值，查询区间最大值以及最大值对应的数量(g_i)，不妨用线段树。

那么最多能拦截的导弹数ans=\max_{i=1}^{n}f1_i，总方案数为\sum_{i=1}^{n}g1_i[f1_i=ans]

至于第二问呢？

先设f2_i表示以i开头的最长不上升子序列，g2_i表示以i开头的的最长不上升子序列的方案

首先：一个导弹被拦截的概率=包含这个导弹的方案数/sum。而一个导弹有可能包含在方案中，当且仅当f1_i+f2_i-1=ans，包含它的方案种数就是g1_i\times g2_i，所以得到：

至于计算f2和g2，把原序列倒过来，并取负数就可以用同一颗线段树了。

注意v或h用数据结构计算的那个要离散化

思路其实是挺简单的，重点是以下部分：

在经过调代码5h后，发现最重要的错误其实在于CDQ的计算顺序问题

下面将以我调代码的心路历程来展现这个问题：

注意：我一开始的写法是用归并排序对h进行排序（用到辅助的数组），v用线段树维护

• 第一阶段：计算顺序

一开始学CDQ的时候，看到的都是这样的：

递归计算左半部分

计算左半部分对右半部分的贡献

递归计算右边部分

我相信很多人学CDQ看的第一道题是归并排序计算逆序对吧？而我们在写归并排序的时候，都是先排序好[l,mid],[mid+1,r]，然后再排序[l,r]的过程中计算逆序对。这并没有任何问题，再加上本人之前做的几道CDQ的问题（P3810 P4169）这样写都不会有锅。就是先计算左右两个部分，再计算左边对右边的贡献。

然而在这道题中这是错的，递归到[l,mid],[mid+1,r]中会计算它内部的相互贡献，然后通过[l,mid]计算对[mid+1,r]的贡献。但会有这种情况，[l,mid]对[mid+1,r]的a计算贡献，然后a对[mid+1,r]的b作出贡献。这样子，按照上面那种计算方法就会有遗漏。也就是说，只有当右边作出的贡献不会受到左边影响时才能先计算左右部分

所以我们调整计算方法，先递归到[l,mid]中，但我们在计算左边对右边的贡献时，类似归并排序，要保证两边的h都是非严格递减的。所以我们只能手动对右半部分排序(sort)

• 数组问题

这个问题与个人的写法有关吧

可能只有我那么傻(⊙_⊙)?

按照上面的，计算左边对右边的贡献是类似归并排序一样的过程，是用两个指针在两个部分扫，把较大的那一个放到数组里（不妨设为w），然后再用w覆盖原数组。这样排序，有可能会让右半部分的排到前面去，这是没有问题的。但问题是，我们要计算右边内部自身的贡献的时候，就不能提前给它排好序，但又要先计算左右的贡献，所以只能开一个临时数组（记为tmp）。对于左半部分递归回来已经排好序了，右半部分只能对tmp手动排序。于此同时，也说明了，w覆盖原数组的步骤应该放在最后进行。

当递归到右半部分[mid+1,r]时，我们调用的是没有排过序的数组，所以右半部分不管怎么变化都还是会在右半部分。注意在这一过程中会修改w数组，当回溯到[l,r]时，w数组就被改得不成人样了。

那怎么解决这个问题呢？既然w数组有问题，那干脆不要w数组了，我们就计算左对右贡献的时候就只计算贡献，而不排序。当最后计算完右边内部自身贡献后，再统一对[l,r]排序。

写得有点乱，看着代码会好一点。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=5e4+10;
int n,tot;
int tmp[N];
struct ask
{
    int t;//位置
    int x;//高度
    int y;//速度
}num[N],v[N],rt[N];//num是一开始输入和倒序的数组，v是CDQ中一层层排序的数组，rt是用来排序右半部分的临时数组
struct node
{
    int maxn;
    double cnt;
    node operator + (const node &a) const//重载加号，方便计算
    {
        if(maxn>a.maxn) return *this;
        if(maxn<a.maxn) return a;
        return (node){maxn,cnt+a.cnt};
    }
}f[N][2];
struct tree
{
    int left,right;
    node val;
}t[4*N];
inline bool cmp1(ask a,ask b)//按照位置排序
{
    return a.t<b.t;
}
inline bool cmp2(ask a,ask b)//按照高度排序
{
    return a.x>b.x;
}
inline void build(int p,int l,int r)//线段树建树
{
    t[p].left=l,t[p].right=r;
    t[p].val=(node){0,0};
    if(l==r) return;
    int mid=(t[p].left+t[p].right)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
}
inline void change(int p,int pos,node c)//单点修改
{
    if(t[p].left==t[p].right)
    {
        t[p].val=t[p].val+c;
        return;
    }
    int mid=(t[p].left+t[p].right)/2;
    if(pos<=mid) change(p*2,pos,c);
    else change(p*2+1,pos,c);
    t[p].val=t[p*2].val+t[p*2+1].val;
}
inline void clear(int p,int pos)//把修改的清空
{
    t[p].val=(node){0,0};
    if(t[p].left==t[p].right) return;
    int mid=(t[p].left+t[p].right)/2;
    if(pos<=mid) clear(p*2,pos);
    else clear(p*2+1,pos);
}
inline node query(int p,int l,int r)//区间查询
{
    if(l<=t[p].left&&r>=t[p].right) return t[p].val;
    int mid=(t[p].left+t[p].right)/2;
    node ans=(node){0,0};
    if(l<=mid) ans=ans+query(p*2,l,r);
    if(r>mid) ans=ans+query(p*2+1,l,r);
    return ans;
}
inline void CDQ(int l,int r,int stg)
{
    if(l==r){ if(f[v[l].t][stg].maxn==0) f[v[l].t][stg]=(node){1,1}; return; }//注意这里不能用+号，而是判断是否为0
    int mid=(l+r)/2,p=l,q=mid+1;
    CDQ(l,mid,stg);//递归计算左半部分
    for(int i=mid+1;i<=r;i++)//把右半部分的塞进临时数组
        rt[i]=v[i];
    sort(rt+mid+1,rt+r+1,cmp2);//对右半部分直接排序
    for(int i=l;i<=r;i++)
    {
        if((p<=mid&&v[p].x>=rt[q].x)||q>r) change(1,v[p].y,f[v[p].t][stg]),p++;
        else 
        { 
            node cmp=query(1,rt[q].y,tot); 
            if(cmp.maxn) cmp.maxn++,f[rt[q].t][stg]=f[rt[q].t][stg]+cmp;//不为0时才更新答案，注意要+1
            q++;
        }
    }
    for(int i=l;i<=mid;i++)
        clear(1,v[i].y);//把修改的清空
    CDQ(mid+1,r,stg);//递归计算右半部分
    sort(v+l,v+r+1,cmp2);//对当前区间[l,r]排序
}
inline void solve(int stg)
{
    for(int i=1;i<=n;i++)
        v[i]=num[i],tmp[i]=num[i].y;
    sort(v+1,v+n+1,cmp1);
    sort(tmp+1,tmp+n+1);
    tot=unique(tmp+1,tmp+n+1)-(tmp+1);
    for(int i=1;i<=n;i++)
        v[i].y=lower_bound(tmp+1,tmp+tot+1,v[i].y)-tmp;//离散化
    build(1,1,tot);
    CDQ(1,n,stg);
}
int main()
{
    int ans=0;
    double sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        num[i].t=i;
        scanf("%d%d",&num[i].x,&num[i].y);
    }
    solve(0);
    for(int i=1;i<=n;i++)
        num[i]=(ask){n-i+1,-num[i].x,-num[i].y};//把数组倒过来，高度和速度取负
    solve(1);
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][0].maxn);//计算最大长度
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(f[i][0].maxn==ans) sum+=f[i][0].cnt;//计算总方案数
    for(int i=1;i<=n;i++)
    {
        if(f[i][0].maxn+f[n-i+1][1].maxn==ans+1) printf("%.5lf ",(f[i][0].cnt*f[n-i+1][1].cnt)/sum);//计算每一个导弹被拦截的概率
        else printf("0.00000 ");
    }
    return 0;
}