P9839 [lg noip D] 四暗刻单骑
Part 1. O(nm)
先观察题目的一些基本性质。
- 交替摸牌，所以每张牌被谁摸到是固定的。
- 因为游戏过程中每个人手里的两张牌都不会相同（不然就结束了），他们一定不会打出和对手手里一样那张牌。所以最后和牌的方式一定是一个人从牌堆中摸到了和自己一样的牌。
- 再考虑两个人手牌一样的情况，他们任何一人都不能丢掉这张牌，不然对面就赢了。因此这种情况的结局是能够直接判定的：判断下一张相同的牌被谁摸到即可，如果没有就是平局。
那么，一个人想和牌，他的策略一定是从某个时刻开始一直拿着某张牌，直到摸到下张一样的。
考虑某个人一直拿着第
- 如果下一张同色的牌被自己摸到，设它的位置是
x 。那么拿着这张牌的结果是在x 时刻胜利。 - 如果下一张同色的牌被对手摸到，对手必然不能把这张牌丢掉。因此双方手牌相同，结局已经确定。
- 再下一张被自己摸到，但因为从
x 时刻开始对面就没有翻盘的机会了，我们记它的结果是在x 时刻直接胜利。 - 被对手摸到，记它的结果是在
x 时刻失败。 - 否则是在
x 时刻达成平局。
- 再下一张被自己摸到，但因为从
那么我们可以在序列上模拟这个过程，如果牌的效果是胜利就选择胜利更早的；失败就选择失败得更晚的，因为可能后面能摸到胜利的牌而翻盘。如果当前已经到达了某个人手里的牌的胜利或失败时刻，则判定答案。
然而直接这样搞并不正确，可怜的樱雪喵写假了一天也没想明白哪里不对。
考虑这样的一组数据：牌堆依次为
Alice 在第一轮是否把牌换成
这启发我们思考一个问题：存在一些情况，如果一个人目标是取得胜利，他就输了；但如果他的目标仅仅是保住平局，却能成功阻止对面赢。这是不能直接贪心判断的。
考虑用如下做法改变他们的目标：先钦定平局算 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 就换牌，即可保证始终不因为输的牌而输掉。
当然这里要特判拿着初始手牌在第一轮就输掉的情况，因为此时他们没有选择权。
因此我们只需判断一段区间内最早赢的牌被谁摸到了。
考虑离线询问，从左向右扫描
那么对于每个询问，最早赢的牌即为区间内最小值所在的位置，判断这张牌位置的奇偶性即可。
我们需要一个数据结构支持单点修改，区间查询最小值和最小值的位置。这里使用线段树维护。
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;
}