P2487 [SDOI2011] 拦截导弹

2018-07-12 16:12:53


这像是一个dp

事实上它是一个三维偏序问题

三个维度分别为高度、编号、速度

和陌上花开类似

第一维排序搞定,第二维用CDQ分治,第三维用树状数组维护

定义 $f[0/1][i]$ 分别为以 $i$ 为开头/结尾的LIS长度

$g[0/1][i]$ 为以 $i$ 为开头/结尾的LIS方案数

树状数组维护这两个值即可

在统计以 $i$ 为结尾时,可以将序列反转,就只需一个CDQ函数就好了

最后统计答案时,若 $f[0][i]+f[1][i]-1==ans$ ,则说明这枚导弹在方案中

它被打下的概率即为有它存在的方案数/总方案数

注意:计算过程中 $g$ 数组必须用double类型,防止爆炸

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef double dd;
const int N=5e4+5;
struct node
{
    dd g[2];
    int h,v,id,f[2]; 
    inline friend bool operator < (node a,node b)
    {
        return a.h==b.h?a.id<b.id:a.h<b.h;
    }
}t[N],d[N];
int n,hy[N],vy[N],cnt1,cnt2,stack[N],top;
struct BIT
{
    int w;
    dd sum;
    BIT(){w=0; sum=0;}
    inline void clear(){w=0; sum=0;}
}c[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
bool cmp(node a,node b){return a.id<b.id;}
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k,dd s)
{
    while (x<=cnt2)
    {
        if (c[x].w<k)
        {
            if (!c[x].w) stack[++top]=x;
            c[x].w=k; c[x].sum=s;
        }
        else if (c[x].w==k) c[x].sum+=s;
        x+=lowbit(x);
    }
}
inline BIT query(int x)
{
    BIT res;
    while (x)
    {
        if (c[x].w>res.w) res=c[x];
        else if (c[x].w==res.w) res.sum+=c[x].sum;
        x-=lowbit(x);
    }
    return res;
}
void CDQ(int l,int r,int k)
{
    if (l==r)
    {
        if (t[l].f[k]<1) t[l].f[k]=t[l].g[k]=1;
        return;
    }
    int mid=(l+r)>>1,p=l,q=mid+1;
    for (reg int i=l;i<=r;i++)
      if (t[i].id<=mid) d[p++]=t[i];
      else d[q++]=t[i];
    for (reg int i=l;i<=r;i++) t[i]=d[i];
    CDQ(l,mid,k); p=l; sort(t+l,t+mid+1);
    for (reg int i=mid+1;i<=r;i++)
    {
        while (p<=mid&&t[i].h>=t[p].h) add(t[p].v,t[p].f[k],t[p].g[k]),++p;
        BIT res=query(t[i].v); if (!res.w) continue;
        if (t[i].f[k]<res.w+1) t[i].f[k]=res.w+1,t[i].g[k]=res.sum;
        else if (t[i].f[k]==res.w+1) t[i].g[k]+=res.sum;
    }
    for (reg int i=1;i<=top;i++) c[stack[i]].clear(); top=0;
    CDQ(mid+1,r,k);
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++)
    {
        t[i].h=read(),t[i].v=read(),t[i].id=i;
        hy[i]=t[i].h; vy[i]=t[i].v;
    }
    sort(hy+1,hy+n+1); sort(vy+1,vy+n+1);
    cnt1=unique(hy+1,hy+n+1)-hy-1;
    cnt2=unique(vy+1,vy+n+1)-vy-1;
    for (reg int i=1;i<=n;i++) t[i].h=cnt1-(lower_bound(hy+1,hy+cnt1+1,t[i].h)-hy)+1;
    for (reg int i=1;i<=n;i++) t[i].v=cnt2-(lower_bound(vy+1,vy+cnt2+1,t[i].v)-vy)+1;
    sort(t+1,t+n+1); CDQ(1,n,0);
    for (reg int i=1;i<=n;i++)
      t[i].h=cnt1-t[i].h+1,t[i].v=cnt2-t[i].v+1,t[i].id=n-t[i].id+1;
    reverse(t+1,t+n+1); sort(t+1,t+n+1); CDQ(1,n,1);
    sort(t+1,t+n+1,cmp); reverse(t+1,t+n+1);
    int ans=0; dd sum=0;
    for (reg int i=1;i<=n;i++)
      if (ans<t[i].f[0]) ans=t[i].f[0],sum=t[i].g[0];
      else if (ans==t[i].f[0]) sum+=t[i].g[0];
    printf("%d\n",ans);
    for (reg int i=1;i<=n;i++)
    {
        int len=t[i].f[0]+t[i].f[1]-1;
        if (len==ans) printf("%.6lf ",t[i].g[0]*t[i].g[1]/sum);
        else printf("0.000000 ");
    }
    return 0;
}