洛谷P2487 [SDOI2011]拦截导弹（cdq分治+dp）

题目链接：传送门

思路：

​ 这个其实就是求三维偏序的最长子序列，且求出每个三元组在所有最长子序列中的出现次数。其中第一维是导弹出现的顺序。

我们先写下dp方程， $fls\left[i\right]$fls[i]为第 i 个元素结尾的最长子序列的长度， $fkind\left[i\right]$fkind[i]为第 i 个元素结尾的最长子序列的方法数。容易写出dp方程 $fls\left[i\right]=max\left(fls\right[i],fls[j]+1)$fls[i]=max(fls[i],fls[j]+1)，其中 $\{j\le i,b_j\le b_i,c_j\le c_i\}${j≤i , bj​≤bi​ , cj​≤ci​}。

对于区间 $(l,r)$(l,r)，设 $m=(l+r)/2$m=(l+r)/2。那么对于i ,j的转移不外乎三种情况：

• $j\in (l,m),i\in (l,m)$j∈(l,m),i∈(l,m)​
• $j\in (l,m),i\in (m+1,r)$j∈(l,m),i∈(m+1,r)​
• $j\in (m+1,r),i\in (m+1,r)$j∈(m+1,r),i∈(m+1,r)

另外总所周知，dp顺序非常重要。

所以我们先计算第一种情况，这个可以使用自身的函数 $cdq(l,m)$cdq(l,m)。

对于第二种转移，我们考虑所有右区间的i，将所有满足 $b_j\&lt;=b_i$bj​<=bi​的 $c_j$cj​加入树状数组中。并维护对应的最大长度和方法数，对于每个 $i$i,我们找 $\le c_i$≤ci​的最大长度，并得到该最大长度的种类数。使用双指针实现所有右区间的 $i$i。

然后计算第三种情况，因为此时右区间的已经不是按照a的大小排列了，但该分治必须要求a有序，所以我们还需大力sort回来。

总的时间复杂度为 $O\left(nlognlogn\right)$O(n logn logn)​。

那么所有的最长子序列的种类就是满足 $fls\left[i\right]==maxlis$fls[i]==maxlis的所有 $fkind\left[i\right]$fkind[i]之和。

根据最终的所有 $fls\left[i\right]$fls[i]，我们可以求出三维偏序最长子序列的长度。

我们再按照同一种方法计算 $gls\left[i\right]$gls[i]和 $gkind\left[i\right]$gkind[i]，代表以第 $i$i个元组开始的三维偏序的最长子序列的长度和方法数。

如果 $gls\left[i\right]+fls\left[i\right]-1==maxlis$gls[i]+fls[i]−1==maxlis，那就证明该元组在其中一个最长子序列中，其出现的次数为 $fkind\left[i\right]\ast gkind\left[i\right]$fkind[i]∗gkind[i]。

注意：

• 种类数会爆long long ，但因为最后求得是分数，所以我们可以用double 储存。
• 树状数组可以维护每个区间相同最大值的方法数.(刚开始以为无法实现，**了)

我太难了-- 2019-9-12 12：10------- 2019-9-13 14：14

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=1e5+20;
int MXN;
struct TreeArray
{
    int mxbt[N];
    double kdbt[N];//初始化都为0
    int lowbit(int k)
    {
        return k&-k;
    }
    void updatemax(int k,int val,double kinds)//种类数
    {
        while(k<=MXN)
        {
            if(mxbt[k] < val)
            {
                mxbt[k]=val;
                kdbt[k]=kinds;
            }
            else if(mxbt[k] == val)
            {
                kdbt[k]+=kinds;
            }
            k+=lowbit(k);
        }
    }
    int getpremax(int k,double &kinds)//返回mx<=k的最大长度和对应的种类数
    {
        int ans=-1;
        kinds=0;
        while(k)
        {
            if(mxbt[k] > ans)
            {
                ans=mxbt[k];
                kinds=kdbt[k];
            }
            else if(mxbt[k]==ans)
                kinds+=kdbt[k];
            k-=lowbit(k);
        }
        return ans;
    }
    void en(int k)//add k的逆过程
    {
        while(k<=MXN)
        {
            mxbt[k]=0;
            kdbt[k]=0;
            k+=lowbit(k);
        }
    }
} hd;
struct node
{
    int a,b,c,fls,gls;//该节点为结尾的偏序长度
    double fkd,gkd;
} t[N];
int n;
bool cmpa(const node& a,const node & b)
{
    if(a.a!=b.a)return a.a<b.a;
    return a.c<b.c;
}
bool gecmpa(const node& a,const node & b)
{
    if(a.a!=b.a) return a.a>b.a;
    return a.c>b.c;
}
bool cmpb(const node &a,const node & b)
{
    return a.b<b.b;
}
bool gecmpb(const node &a,const node & b)
{
    return a.b>b.b;
}
bool cmpc(const node &a,const node & b)
{
    return a.c<b.c;
}
void cdq1(int l,int r)
{
// printf("l:%d,r:%d\n",l,r);
    if(r==l) return ;
    int m=(l+r)>>1;
    cdq1(l,m);
    sort(t+l,t+m+1,cmpb);
    sort(t+m+1,t+r+1,cmpb);
    int p=l-1;
    for(int i=m+1; i<=r; ++i)
    {
        while(p+1<=m&&t[p+1].b<=t[i].b)
        {
            ++p;
            hd.updatemax(t[p].c,t[p].fls,t[p].fkd);
        }
        int fls;
        double fkd;
        fls=hd.getpremax(t[i].c,fkd);
        if(fls==0) continue;
        if(fls+1 > t[i].fls)
        {
            t[i].fls=fls+1;
            t[i].fkd=fkd;
        }
        else if(fls+1 == t[i].fls)
            t[i].fkd+=fkd;
    }
    for(int i=l; i<=p; ++i)
        hd.en(t[i].c);
    sort(t+m+1,t+r+1,cmpa);
    cdq1(m+1,r);
}
void cdq2(int l,int r)
{
    if(r==l) return ;
    int m=(l+r)>>1;
    cdq2(l,m);
    sort(t+l,t+m+1,gecmpb);
    sort(t+m+1,t+r+1,gecmpb);
    int p=l-1;
    for(int i=m+1; i<=r; ++i)
    {
        while(p+1<=m&&t[p+1].b>=t[i].b)
        {
            ++p;
            hd.updatemax(n-t[p].c+1,t[p].gls,t[p].gkd);
        }
        int gls;
        double gkd;
        gls=hd.getpremax(n-t[i].c+1,gkd);
        if(gls==0) continue;
        if(gls+1 > t[i].gls)
        {
            t[i].gls=gls+1;
            t[i].gkd=gkd;
        }
        else if(gls+1 == t[i].gls)
            t[i].gkd+=gkd;
    }
    for(int i=l; i<=p; ++i)
        hd.en(n-t[i].c+1);
    sort(t+m+1,t+r+1,gecmpa);
    cdq2(m+1,r);
}
int main()
{
    scanf("%d",&n);
    MXN=n;
    for(int i=1; i<=n; ++i)
    {
        int h,v;
        scanf("%d%d",&h,&v);
        t[i].a=-h;
        t[i].b=-v;
        t[i].c=i;
        t[i].fls=1;
        t[i].fkd=1.0;
        t[i].gls=1;
        t[i].gkd=1.0;
    }//h为第一维度
    sort(t+1,t+n+1,cmpa);
    cdq1(1,n);
    int mxlis=-1;
    for(int i=1; i<=n; ++i)
        mxlis=max(mxlis,t[i].fls);
    sort(t+1,t+n+1,gecmpa);
    cdq2(1,n);
    printf("%d\n",mxlis);
    double sum=0;
    for(int i=1;i<=n;++i)
        if(t[i].fls==mxlis) sum+=t[i].fkd;
    sort(t+1,t+1+n,cmpc);
    for(int i=1; i<=n; ++i)
    {
        if(t[i].fls+t[i].gls-1==mxlis)
        {
            printf("%.5f ",t[i].fkd*t[i].gkd/sum);
        }
        else printf("0.00000 ");
    }
}

• KaTeX parse error: Can't use function '\r' in math mode at position 2: i\̲r̲