自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 22:52:18，当前版本为作者最后更新于2023-11-11 19:46:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part 1. $O(nm)$

先观察题目的一些基本性质。

• 交替摸牌，所以每张牌被谁摸到是固定的。
• 因为游戏过程中每个人手里的两张牌都不会相同（不然就结束了），他们一定不会打出和对手手里一样那张牌。所以最后和牌的方式一定是一个人从牌堆中摸到了和自己一样的牌。
• 再考虑两个人手牌一样的情况，他们任何一人都不能丢掉这张牌，不然对面就赢了。因此这种情况的结局是能够直接判定的：判断下一张相同的牌被谁摸到即可，如果没有就是平局。

那么，一个人想和牌，他的策略一定是从某个时刻开始一直拿着某张牌，直到摸到下张一样的。

考虑某个人一直拿着第 $i$ 张牌会产生什么效果：

• 如果下一张同色的牌被自己摸到，设它的位置是 $x$。那么拿着这张牌的结果是在 $x$ 时刻胜利。
• 如果下一张同色的牌被对手摸到，对手必然不能把这张牌丢掉。因此双方手牌相同，结局已经确定。
  • 再下一张被自己摸到，但因为从 $x$ 时刻开始对面就没有翻盘的机会了，我们记它的结果是在 $x$ 时刻直接胜利。
  • 被对手摸到，记它的结果是在 $x$ 时刻失败。
  • 否则是在 $x$ 时刻达成平局。

那么我们可以在序列上模拟这个过程，如果牌的效果是胜利就选择胜利更早的；失败就选择失败得更晚的，因为可能后面能摸到胜利的牌而翻盘。如果当前已经到达了某个人手里的牌的胜利或失败时刻，则判定答案。

然而直接这样搞并不正确，可怜的樱雪喵写假了一天也没想明白哪里不对。

考虑这样的一组数据：牌堆依次为 $3,1,4,3,4$，初始手牌为 $1,2$。
Alice 在第一轮是否把牌换成 $3$ 都是平局，她更希望等到后面胜利。而 Bob 如果寄希望于后面胜利，不选择把 $2$ 换成 $1$，他最后只能失败。而如果他的目标是平局，他会摸走牌堆中的 $1$，并成功平局。
这启发我们思考一个问题：存在一些情况，如果一个人目标是取得胜利，他就输了；但如果他的目标仅仅是保住平局，却能成功阻止对面赢。这是不能直接贪心判断的。

考虑用如下做法改变他们的目标：先钦定平局算 Alice 赢，这等价于 Alice 的目标是保住平局。如果此时 Bob 仍然能赢，才算作 Bob 必胜。反之同理。
如果正反都不满足条件，则说明存在一种方式使本来要输的人保住平局，答案为平局。

细节想不清楚的话很容易写假，可以参考代码理解。

const int N=2e5+5;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
    auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
    if(qwq==pos[x].end()||(*qwq)>r) return -1;
    return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
    int qwq=find(x,l+fg,r);
    if(qwq==-1) return (l&1)==flag?n+1:-n-1;
    if((qwq&1)==(l&1)) return qwq;
    int nqwq=find(x,qwq,r);
    if(nqwq==-1) return (l&1)==flag?qwq:-qwq;
    else if((nqwq&1)==(l&1)) return qwq;
    else return -qwq;
}
il int solve(int x,int y,int l,int r)
{
    if(x==y)
    {
        int nxt=find(x,l-1,r);
        if(nxt==-1) return flag?1:-1;
        else if((nxt&1)==(l&1)) return 1;
        else return -1;
    }
    int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
    for(int i=l;i<=r;i++)
    {
        if(wx==i) return 1; if(wy==i) return -1;
        if(-wx==i) return -1; if(-wy==i) return 1;
        if(x==y)
        {
            int nxt=find(x,i-1,r);
            if(nxt==-1) return flag?1:-1;
            else if((nxt&1)==(l&1)) return 1;
            else return -1;
        }
        if((i&1)==(l&1))
        {
            int nxt=getw(a[i],i,r);
            if(nxt>0&&(nxt<wx||wx<0)) wx=nxt,x=a[i];
            else if(nxt<0&&wx<0&&nxt<wx) wx=nxt,x=a[i];
        }
        else 
        {
            int nxt=getw(a[i],i,r);
            if(nxt>0&&(nxt<wy||wy<0)) wy=nxt,y=a[i];
            else if(nxt<0&&wy<0&&nxt<wy) wy=nxt,y=a[i];
        }
    }
    return flag?1:-1;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]].push_back(i);
    while(m--)
    {
        id++;
        int x=read(),y=read(),l=read(),r=read();
        flag=1; int res1=solve(x,y,l,r);
        flag=0; int res0=solve(x,y,l,r);
        if(res1==-1) printf("B\n");
        else if(res0==1) printf("A\n"); else printf("D\n");
    }
    return 0;
}

Part 2. $O((n+m)\log n)$

假设每张牌的结局是已经确定的，依旧不容易快速地维护答案，因为输了要尽可能晚输，赢了又要尽可能早赢。

我们继续观察性质。

注意到，到达某张手牌判定答案的时刻时，被判定的一定是赢的那张牌。换句话说，一个人必然不会一直拿着一张输的牌，直到因为这张牌而输掉。

考虑证明这个结论。假设 Alice 现在手里拿着一张输的牌，并且下一轮就要输了；这时候她又摸到了另一张要输的牌。因为这两张牌不同，它们输的位置也一定不同。那么新摸的这张牌一定输得比原来那张要晚。每当出现这种情况 Alice 就换牌，即可保证始终不因为输的牌而输掉。
当然这里要特判拿着初始手牌在第一轮就输掉的情况，因为此时他们没有选择权。

因此我们只需判断一段区间内最早赢的牌被谁摸到了。

考虑离线询问，从左向右扫描 $r$。对于在 $i$ 位置的牌，它的贡献只与它下一张相同的牌、下下张相同的牌是否在区间内有关。因此一张牌的贡献只会改变 $3$ 次，可以每次修改暴力求新值。
那么对于每个询问，最早赢的牌即为区间内最小值所在的位置，判断这张牌位置的奇偶性即可。

我们需要一个数据结构支持单点修改，区间查询最小值和最小值的位置。这里使用线段树维护。

const int N=2e5+5,inf=1e9;
int id,n,m,k,a[N],flag;
vector<int> pos[N];
il int find(int x,int l,int r)
{
    auto qwq=upper_bound(pos[x].begin(),pos[x].end(),l);
    if(qwq==pos[x].end()||(*qwq)>r) return -1;
    return *qwq;
}
il int getw(int x,int l,int r,int fg=0)
{
    int qwq=find(x,l+fg,r);
    if(qwq==-1) return inf;
    if((qwq&1)==(l&1)) return qwq;
    int nqwq=find(x,qwq,r);
    if(nqwq==-1) return (l&1)==flag?qwq:inf;
    else if((nqwq&1)==(l&1)) return qwq;
    else return inf;
}
struct segtree
{
    struct node{int mn,pos;} tr[N<<2];
    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid (l+r>>1)
    il node pushup(const node &l,const node &r)
    {
        if(l.mn<r.mn) return l;
        else return r;
    }
    void build(int x,int l,int r) 
    {
        if(l==r) {tr[x]={inf,l};return;}
        build(ls,l,mid),build(rs,mid+1,r);
        tr[x]=pushup(tr[ls],tr[rs]);
    }
    void upd(int x,int l,int r,int p,int k)
    {
        if(l==r) {tr[x]={k,l};return;}
        if(p<=mid) upd(ls,l,mid,p,k);
        else upd(rs,mid+1,r,p,k);
        tr[x]=pushup(tr[ls],tr[rs]);
    }
    node query(int x,int l,int r,int ml,int mr) 
    {
        if(l==ml&&r==mr) return tr[x];
        if(mr<=mid) return query(ls,l,mid,ml,mr);
        else if(ml>mid) return query(rs,mid+1,r,ml,mr);
        else return pushup(query(ls,l,mid,ml,mid),query(rs,mid+1,r,mid+1,mr));
    }
}seg;
int ans[2][N];
vector<int> nd[N];
struct node{int x,y,l,r,id;};
vector<node> q[N];
il int calc(int x,int y,int l,int r)
{
    if(x==y)
    {
        int nxt=find(x,l-1,r);
        if(nxt==-1) return flag?1:-1;
        else if((nxt&1)==(l&1)) return 1;
        else return -1;
    }
    if(y==a[l])
    {
        int nxt=find(y,l,r);
        if(nxt!=-1&&((nxt&1)==(l&1))) return 1;
        else if(nxt==-1) return flag?1:-1;
    }
    int wx=getw(x,l-2,r,1),wy=getw(y,l-1,r);
    int ans=min(wx,wy),pos=(wx<wy)?l-2:l-1;
    segtree::node qwq=seg.query(1,1,n,l,r);
    if(qwq.mn<ans) ans=qwq.mn,pos=qwq.pos;
    if(ans==inf) return flag?1:-1;
    return ((l&1)==(pos&1))?1:-1;
}
void solve()
{
    seg.build(1,1,n);
    for(int r=1;r<=n;r++)
    {
        for(auto x:nd[r]) seg.upd(1,1,n,x,getw(a[x],x,r));
        for(auto i:q[r])
        {
            int x=i.x,y=i.y,l=i.l,r=i.r,id=i.id;
            ans[flag][id]=calc(x,y,l,r);
        }
    }
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]].push_back(i);
    for(int i=1;i<=m;i++) 
    {
        int x=read(),y=read(),l=read(),r=read();
        q[r].push_back({x,y,l,r,i});
    }
    for(int i=1;i<=n;i++) 
    {
        int nxt=find(a[i],i,n);
        if(nxt==-1) continue;
        nd[nxt].push_back(i);
        int nnxt=find(a[i],nxt,n);
        if(nnxt!=-1) nd[nnxt].push_back(i);
    }
    for(flag=0;flag<2;flag++) solve();
    for(int i=1;i<=m;i++)
    {
        if(ans[1][i]==-1) printf("B");
        else if(ans[0][i]==1) printf("A");
        else printf("D");
        printf("\n");
    }
    return 0;
}