出题人题解 | #虎龙斗#

因为 中选出的士兵可以交错排布，所以我们需要先讨论从 中分别选出多少士兵。
假设从 中选出 人，从 中选出 人（) ，我们先要在各个数组中尽量选出最大的冲锋序列，然后在将两个冲锋序列合并即可。
对于选出最大的冲锋序列，我们可以用单调栈完成（栈底到栈顶的元素递减）；对于合并，我们可以用双指针完成（有点类似于归并排序合并的算法吧）。
时间复杂度： , 是得到最大冲锋序列的复杂度，而在比较时有 次合并，每次因为要比较整个剩余序列（见 std )所以为 ,又因为要枚举 ，因此总体要乘上 。

实际内测的时候就被dalao们各路吊打了。首先复杂度的比较次数应该是加起来等于 的，因此 std 做法的时间远远打不打 级别。 然后内测的dalao随便给出了 带 的做法，吊打了 std. 但是考虑到这是道 T2，还是要以给分为目的，就没有加强数据范围。

实际上比赛的时候，这题实现可能有一定难度，通过量居然低于 C 题。

联合出题人： 长郡中学 Werner_yin

#include<bits/stdc++.h>
const int N=5e5+500;

int gti(void)
{
    char c=getchar();
    int ret=0,st=1;
    for (;c!='-'&&!isdigit(c);c=getchar());
    if (c=='-') st=-1,c=getchar();
    for (;isdigit(c);c=getchar()) ret=ret*10+c-'0';
    return ret*st;
}

struct P
{
    int val,loc;
    bool operator<(const P &b)const
    {
        if (val!=b.val) return val<b.val;
        return loc<b.loc;
    }
};
struct segt
{
    int mx[N<<2],n;
#define mid ((l+r)>>1)
    void build(int *arr,int v,int l,int r)
    {
        if (l==r) mx[v]=arr[l];
        else
        {
            build(arr,v<<1,l,mid);
            build(arr,v<<1|1,mid+1,r);
            mx[v]=std::max(mx[v<<1],mx[v<<1|1]);
        }
    }
    int query(int ql,int qr,int v,int l,int r)
    {
        if (ql<=l&&qr>=r) return mx[v];
        int ret=-1;
        if (ql<=mid) ret=std::max(ret,query(ql,qr,v<<1,l,mid));
        if (qr>mid) ret=std::max(ret,query(ql,qr,v<<1|1,mid+1,r));
        return ret;
    }
#undef mid
};
struct Arr
{
    segt tr;
    std::set<P> st;
    int n,a[N];
    void init(int len)
    {
        for (int i=1;i<=len;i++)
            a[i]=gti(),st.insert((P){a[i],i});
        n=len;
        tr.build(a,1,1,n);
    }
    P getNext(int now,int lim)
    {
        if (now+1>n-lim) return (P){-1,0};
        int mx=tr.query(now+1,n-lim,1,1,n);
        P v=*st.lower_bound((P){mx,now+1});
        return v;
    }
    int rest(int now)
    {
        return n-now;
    }
}t[2];

struct Q
{
    int x,y,val;
    Q left(int need)
    {
        P a=t[0].getNext(x,std::max(0,need-1-t[1].rest(y)));
        return (Q){a.loc,y,a.val};
    }
    Q right(int need)
    {
        P b=t[1].getNext(y,std::max(0,need-1-t[0].rest(x)));
        return (Q){x,b.loc,b.val};
    }
}stk[N],tmp[N<<1];
int rt[N];
int tot=0;

int main(void)
{
    int n=gti(),m=gti(),l=gti();
    t[0].init(n),t[1].init(m);
    stk[++tot]=(Q){0,0,0};
    for (int i=1;i<=l;i++)
    {
        int nxt=0,ans=-1;
        for (int j=1;j<=tot;j++)
        {
            tmp[++nxt]=stk[j].left(l-i+1);
            ans=std::max(ans,tmp[nxt].val);
            tmp[++nxt]=stk[j].right(l-i+1);
            ans=std::max(ans,tmp[nxt].val);
        }
        printf("%d%c",ans," \n"[i==l]);
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans)
                rt[tmp[j].x]=tmp[j].y;;
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans)
                rt[tmp[j].x]=std::min(rt[tmp[j].x],tmp[j].y);
        tot=0;
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans&&tmp[j].y==rt[tmp[j].x])
                stk[++tot]=tmp[j],rt[tmp[j].x]=-1;
    }
    return 0;
}

再给一个内测的时间复杂度更优的做法：

#include<bits/stdc++.h>
const int N=5e5+500;

int gti(void)
{
    char c=getchar();
    int ret=0,st=1;
    for (;c!='-'&&!isdigit(c);c=getchar());
    if (c=='-') st=-1,c=getchar();
    for (;isdigit(c);c=getchar()) ret=ret*10+c-'0';
    return ret*st;
}

struct P
{
    int val,loc;
    bool operator<(const P &b)const
    {
        if (val!=b.val) return val<b.val;
        return loc<b.loc;
    }
};
struct segt
{
    int mx[N<<2],n;
#define mid ((l+r)>>1)
    void build(int *arr,int v,int l,int r)
    {
        if (l==r) mx[v]=arr[l];
        else
        {
            build(arr,v<<1,l,mid);
            build(arr,v<<1|1,mid+1,r);
            mx[v]=std::max(mx[v<<1],mx[v<<1|1]);
        }
    }
    int query(int ql,int qr,int v,int l,int r)
    {
        if (ql<=l&&qr>=r) return mx[v];
        int ret=-1;
        if (ql<=mid) ret=std::max(ret,query(ql,qr,v<<1,l,mid));
        if (qr>mid) ret=std::max(ret,query(ql,qr,v<<1|1,mid+1,r));
        return ret;
    }
#undef mid
};
struct Arr
{
    segt tr;
    std::set<P> st;
    int n,a[N];
    void init(int len)
    {
        for (int i=1;i<=len;i++)
            a[i]=gti(),st.insert((P){a[i],i});
        n=len;
        tr.build(a,1,1,n);
    }
    P getNext(int now,int lim)
    {
        if (now+1>n-lim) return (P){-1,0};
        int mx=tr.query(now+1,n-lim,1,1,n);
        P v=*st.lower_bound((P){mx,now+1});
        return v;
    }
    int rest(int now)
    {
        return n-now;
    }
}t[2];

struct Q
{
    int x,y,val;
    Q left(int need)
    {
        P a=t[0].getNext(x,std::max(0,need-1-t[1].rest(y)));
        return (Q){a.loc,y,a.val};
    }
    Q right(int need)
    {
        P b=t[1].getNext(y,std::max(0,need-1-t[0].rest(x)));
        return (Q){x,b.loc,b.val};
    }
}stk[N],tmp[N<<1];
int rt[N];
int tot=0;

int main(void)
{
    int n=gti(),m=gti(),l=gti();
    t[0].init(n),t[1].init(m);
    stk[++tot]=(Q){0,0,0};
    for (int i=1;i<=l;i++)
    {
        int nxt=0,ans=-1;
        for (int j=1;j<=tot;j++)
        {
            tmp[++nxt]=stk[j].left(l-i+1);
            ans=std::max(ans,tmp[nxt].val);
            tmp[++nxt]=stk[j].right(l-i+1);
            ans=std::max(ans,tmp[nxt].val);
        }
        printf("%d%c",ans," \n"[i==l]);
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans)
                rt[tmp[j].x]=tmp[j].y;;
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans)
                rt[tmp[j].x]=std::min(rt[tmp[j].x],tmp[j].y);
        tot=0;
        for (int j=1;j<=nxt;j++)
            if (tmp[j].val==ans&&tmp[j].y==rt[tmp[j].x])
                stk[++tot]=tmp[j],rt[tmp[j].x]=-1;
    }
    return 0;
}

此外，此题还可以用 DP 通过。不再赘述