P9839 四暗刻单骑

· · 题解

题解参考了 here。

Solution

1. x=y

2. \mathcal O(nm\log n)

（\log 来自二分）

//52 分暴力
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,k,a[N],o,x,y,l,r;   //o=1/0：平局算 Alice/Bob 赢
vector<int>v[N];
array<int,2>A,B;
bool calc(int l,int r,int x){   //x=y，牌堆为 [l,r]，结局是什么
    int i=*lower_bound(v[x].begin(),v[x].end(),l);
    return i>r?o:i&1;
}
array<int,2> get(int who,int i,int x){  //当前 who 取第 i 张牌（who=1/0: Alice/Bob），第 i 张牌数字是 x，这张牌对应的 (time,op=1/0: Alice/Bob 赢)
    int j=*upper_bound(v[x].begin(),v[x].end(),i),op;
    if(j>r) op=o;
    else{
        if((j&1)==who) op=who;
        else op=calc(j+1,r,x);
    }
    return {j,op};
}
bool work(){
    if(x==y) return calc(l,r,x);
    A=get(1,l-1,x),B=get(0,l-1,y);
    for(int i=l;i<=r;i++){
        auto p=get(i&1,i,a[i]);
        if(i&1){
            if(p[1]>A[1]||(p[1]==A[1]&&((p[1]&&p[0]<A[0])||(!p[1]&&p[0]>A[0])))) A=p;
        }
        else
            if(p[1]<B[1]||(p[1]==B[1]&&((!p[1]&&p[0]<B[0])||(p[1]&&p[0]>B[0])))) B=p;
        if(A[0]==i) return A[1];
        if(B[0]==i) return B[1];
    }
    return o;
}
signed main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),v[a[i]].push_back(i);
    for(int i=1;i<=k;i++) v[i].push_back(n+1);
    while(m--){
        scanf("%d%d%d%d",&x,&y,&l,&r);
        int a,b;
        o=0,a=work(),o=1,b=work();
        puts(a?"A":(!b?"B":"D"));
    }
    return 0;
}

3. \mathcal O((n+m)\log n)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,k,a[N],r,o,ans[2][N];
vector<int>v[N],upd[N];
array<int,2>A,B,mn[N<<2];
vector<array<int,4> >q[N];
bool calc(int l,int r,int x){
    int i=*lower_bound(v[x].begin(),v[x].end(),l);
    return i>r?o:i&1;
}
array<int,2> get(int who,int i,int x){
    int j=*upper_bound(v[x].begin(),v[x].end(),i),op;
    if(j>r) j=n+1,op=o;
    else{
        if((j&1)==who) op=who;
        else op=calc(j+1,r,x);
    }
    return {j,op};
}
void modify(int p,int l,int r,int pos,int v){
    if(l==r){mn[p]={v,l};return ;}
    int mid=(l+r)/2;
    if(pos<=mid) modify(p<<1,l,mid,pos,v);
    else modify(p<<1|1,mid+1,r,pos,v);
    mn[p]=min(mn[p<<1],mn[p<<1|1]);
}
auto query(int p,int l,int r,int lx,int rx){
    if(l>=lx&&r<=rx) return mn[p];
    int mid=(l+r)/2;
    array<int,2>ans={n+2,0};
    if(lx<=mid) ans=query(p<<1,l,mid,lx,rx);
    if(rx>mid) ans=min(ans,query(p<<1|1,mid+1,r,lx,rx));
    return ans;
}
signed main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),v[a[i]].push_back(i);
    for(int i=1;i<=k;i++)
        v[i].push_back(n+1),v[i].push_back(n+2);
    for(int i=1;i<=n;i++){
        int j=*upper_bound(v[a[i]].begin(),v[a[i]].end(),i),
        k=*upper_bound(v[a[i]].begin(),v[a[i]].end(),j);
        for(int x:{i,j,k}) upd[x].push_back(i);
    }
    for(int i=1,x,y,l;i<=m;i++)
        scanf("%d%d%d%d",&x,&y,&l,&r),q[r].push_back({x,y,l,i});
    for(o=0;o<2;o++){
        for(int i=1;i<=(n<<2);i++) mn[i][0]=1e9;
        for(r=1;r<=n;r++){
            for(int i:upd[r]){
                auto p=get(i&1,i,a[i]);
                modify(1,1,n,i,p[1]==(i&1)?p[0]:1e9);
            }
            for(auto i:q[r]){
                int x=i[0],y=i[1],l=i[2],&f=ans[o][i[3]];
                if(x==y){f=calc(l,r,x);continue;}
                A=get(1,l-1,x),B=get(0,l-1,y);
                if(A[0]==l) f=A[1];
                else if(B[0]==l) f=B[1];
                else{
                    auto x=query(1,1,n,l,r);
                    if(A[1]) x=min(x,{A[0],1});
                    if(!B[1]) x=min(x,{B[0],0});
                    f=x[0]<=r?x[1]&1:o;
                }
            }
        }
    }
    for(int i=1;i<=m;i++)
        puts(ans[0][i]?"A":(!ans[1][i]?"B":"D"));
    return 0;
}

有错请指出 qwq。