决斗 题解

赛题来自 OIFHA 第四场模拟赛。

原题展现

青蛙哥与名侦探柯南正在进行一场对决。

他们两个人每人有 \(n\) 张牌，每张牌有一个点数。

并且在接下来的 \(n\) 个回合中每回合青蛙哥与名侦探柯南两人会各自打出一张牌。

每回合裁判会检查，打出的牌点数更高的一方获胜从而得到一分，如果二人点数相同，则不得分。

然而现在青蛙哥通过偷看的方法得到了名侦探柯南的出牌顺序，他可以任意定一个自己的出牌的顺序。

他首先希望让自己的得分尽可能高，然后就是希望在让自己的得分尽可能高这个前提下，最大化自己从第一回合开始到最后一个回合结束过程中，每回合出牌点数构成的字符串的字典序。

数据范围：\(n,a_i\leq 10^5\)。

Solution

首先假设我们已经得知青蛙最高得分是多少。

对于第 \(i\) 回合，考虑让不让青蛙在这个回合赢。

如果赢的话，可以取最大的 \(b_j\)，也可以取只比 \(a_i\) 大一点的 \(b_j\)。

如果不让他赢，可以取最小的 \(b_j\)，也可以取只比 \(a_i\) 小一点的 \(b_j\)。

可见，让青蛙在这个回合赢或输，可取的值都是一个 \([l,r]\) 区间。题目要求字典序最大，而我们也不能直接确定青蛙在这个区间取多少时字典序最大。所以这里需要二分答案。

至于一开始的假设：“已经得知最高得分”，这个怎么实现呢？

可以考虑维护一棵权值线段树，每个节点都是一个三元组 \((s,s_1,s_2)\)。分别表示：青蛙哥的得分，柯南的牌数，青蛙的牌数。

在合并区间的时候，肯定是拿青蛙点数大的牌去对抗柯南点数小的牌。得分就是 tr[rt].s=tr[lson].s+tr[rson].s+k，其中 k=min(tr[lson].s1,tr[rson].s2)。

时间复杂度 \(O(n\log^2 V)\)，\(V\) 是值域。

code

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ls rt<<1
#define rs ls|1

const int MAXN=1e5+5,m=1e5;

int n;
int a[MAXN],b[MAXN];
struct tree
{
    int s,s1,s2;
}tr[MAXN<<2];
multiset<int> s;

void pushup(int rt)
{
    int minz=min(tr[ls].s1,tr[rs].s2);
    tr[rt].s=tr[ls].s+tr[rs].s+minz;
    tr[rt].s1=tr[ls].s1+tr[rs].s1-minz;
    tr[rt].s2=tr[ls].s2+tr[rs].s2-minz;
}

void update(int rt,int l,int r,int x,int v1,int v2)
{
    if(l==r)
    {
        tr[rt].s1+=v1;
        tr[rt].s2+=v2;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) update(ls,l,mid,x,v1,v2);
    else update(rs,mid+1,r,x,v1,v2);
    pushup(rt);
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]),s.insert(b[i]);

    for(int i=1;i<=n;i++)
        update(1,1,m,a[i],1,0),update(1,1,m,b[i],0,1);

    int cnt=tr[1].s;
    for(int i=1;i<=n;i++)
    {
        update(1,1,m,a[i],-1,0);
        int l=a[i]+1,r=*s.rbegin(),mid,ans;
        while (l<=r)
        {
            mid=l+r>>1;
            update(1,1,m,mid,0,-1);
            if(tr[1].s+1==cnt) l=mid+1,ans=mid;
            else r=mid-1;
            update(1,1,m,mid,0,1);
        }
        update(1,1,m,ans,0,-1);
        if(a[i]<*s.rbegin()&&tr[1].s+1==cnt)
        {
            --cnt;
            printf("%lld ",ans);
            s.erase(s.find(ans));
        }
        else
        {
            update(1,1,m,ans,0,1);
            l=1,r=a[i],ans=l;
            while (l<=r)
            {
                mid=l+r>>1;
                update(1,1,m,mid,0,-1);
                if(tr[1].s==cnt) l=mid+1,ans=mid;
                else r=mid-1;
                update(1,1,m,mid,0,1);
            }
            update(1,1,m,ans,0,-1);
            printf("%lld ",ans);
            s.erase(s.find(ans));
        }
    }

    return 0;
}