题解：P12073 [OOI 2025] Alice, Bob, and two arrays.

· · 题解

我们发现直接记录的状态数是 \mathcal{O}(NM)，可以直接使用 boolean 的 dp 去做而不用 SG 函数。

建出子序列自动机后暴力转移复杂度是 \mathcal{O}(NMk)，过不去第二档分，考虑优化。

从后面的 0 往前面的 1 贡献，记录 lst,nxt 数组分别表示两个序列中某个位置的数上一次/下一次的出现位置，于是转移形态即为 x\in[lst_i,i),y\in[lst_j,j)\leftarrow i,j，可以用前缀和优化做到 \mathcal{O}(NM)。

接下来考虑怎么处理连续段，由于我们记录不了所有的状态，只能考虑记录一些特殊的状态并考虑它们之间的转移。

很明显每对连续段的开头是很重要的，它能不能直接转移呢？

首先连续段之间的转移（即加入与当前段不相同的字符）是容易的，运用前面那种方法即可转移。

剩下的是加上跟当前段相同的字符，这一部分有两种转移：

我们发现这两种转移大概率都转移到的不是我们记录下来的状态，但也有一个好处是一直加的是同一个字符，于是我们一直往后跳的复杂度是可接受的。

现在的复杂度是 \mathcal{O}(n^3)，我们考虑优化往后跳的过程。

注意到我们会在一个 g_{x,y}=1 的位置停下来，其中 g 表示这个段后继是否有 0，先手到这个位置就会直接走到 0，否则会继续走到下一段。

把同种颜色的数字拿出来标号，一个 g 作用到的范围是一个矩形，而上面不断往后跳的过程就是一个斜线。

把询问挂在点上，从大往小扫描，每次相当于一个矩形更新查询一个斜线射线第一次与矩形有交的位置，一个矩形能贡献到的斜线是一个区间，由于我们是从大往小扫的，直接区间 cmin 一个 pair 然后单点查询。

找到第一个位置后判断走的路径长度奇偶性即可，时间复杂度 \mathcal{O}((nm+q)\log \max(N,M))。

#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#undef ll
using i64 = int;
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
const int maxn = 1600+5;
const int maxq = 1e6+5;
const i64 oo = 1e9;
i64 cA[maxn],cB[maxn],pA[maxn],pB[maxn];
i64 sum[maxn][maxn],nxtA[maxn],nxtB[maxn],nxt[maxn];
i64 n,m,k,q,A[maxn],B[maxn],lA[maxn],lB[maxn],sA[maxn],sB[maxn];
i64 lstA[maxn],lstB[maxn],lst[maxn],g[maxn][maxn],f[maxn][maxn];

vector<i64>lsh[maxn];
#define pii pair<i64,i64>
IV cmin(pii&x,pii val){x>val?x=val,0:0;}
struct zkw{
    vector<pair<i64,i64> >mn;i64 n;
    IV init(i64 L){
        mn.resize(2*L);n=L;
        F(i,1,2*L-1)mn[i]=make_pair(oo,oo);
    }
    IV chg(i64 l,i64 r,pii v){
        l++;r++;
        for(l+=n-1,r+=n-1;l<=r;l>>=1,r>>=1){
            if( (l&1))cmin(mn[l++],v);
            if(!(r&1))cmin(mn[r--],v);
        }
    }
    pii Q(i64 p){
        p++;
        pii Ans=make_pair(oo,oo);
        for(p+=n-1;p;p>>=1)Ans=min(Ans,mn[p]);
        return Ans;
    }
}nb[maxn];
map<i64,pair<i64,i64> >mp[maxn];
IV upd(i64 t,i64 x,pair<i64,i64>v){
    if(mp[t].count(x))mp[t][x]=min(mp[t][x],v);
    else mp[t][x]=v;
}
i64 calc(i64 x,i64 y,i64 cx,i64 cy){
    i64 px=pA[x]+cx-1,py=pB[y]+cy-1;
    return px-py;
}
bool Q(i64 x,i64 y,i64 cx,i64 cy){
    if(g[x][y])return 1;
    if(x==n+1||y==m+1)return 1;

    i64 px=pA[x]+cx-1,py=pB[y]+cy-1;
    i64 t=lower_bound(lsh[A[x]].begin(),lsh[A[x]].end(),px-py)-lsh[A[x]].begin();
    pii v=nb[A[x]].Q(t);
    if(v.first==oo){
        i64 len=min(cA[A[x]]-px+1,cB[B[y]]-py+1);
        return !(len&1);
    }
    auto[ex,ey]=v;
    i64 len=max(pA[ex]-px,pB[ey]-py);
    return!(len&1);
}

bool Ans[maxq];
vector<array<i64,3> >qwq[maxn][maxn];
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);

    read();n=read();
    read();m=read();
    k=read();q=read();
    F(i,1,n){
        sA[i]=(lA[i]=read())+sA[i-1],A[i]=read();
        pA[i]=cA[A[i]]+1;cA[A[i]]+=lA[i];
    }
    F(i,1,m){
        sB[i]=(lB[i]=read())+sB[i-1],B[i]=read();
        pB[i]=cB[B[i]]+1;cB[B[i]]+=lB[i];
    }
    mem(lst,0);
    F(i,1,n){
        lstA[i]=lst[A[i]];
        lst[A[i]]=i;
    }
    F(i,1,k)nxt[i]=n+1;
    D(i,n,1){
        nxtA[i]=nxt[A[i]];
        nxt[A[i]]=i;
    }
    mem(lst,0);
    F(i,1,m){
        lstB[i]=lst[B[i]];
        lst[B[i]]=i;
    }
    F(i,1,k)nxt[i]=m+1;
    D(i,m,1){
        nxtB[i]=nxt[B[i]];
        nxt[B[i]]=i;
    }
    F(o,1,q){
        i64 x=read(),y=read();
        if(x==sA[n]&&y==sB[m])continue;
        x++;y++;
        i64 px=lower_bound(sA+1,sA+1+n,x)-sA;
        i64 py=lower_bound(sB+1,sB+1+m,y)-sB;
        qwq[px][py].push_back({x-sA[px-1]-1,y-sB[py-1]-1,o});
    }
    F(i,1,n)F(j,1,m)if(A[i]==B[j]){
        lsh[A[i]].push_back(calc(i,j,1,1));
        for(auto[x,y,o]:qwq[i][j])
            lsh[A[i]].push_back(calc(i,j,x,y));
    }
    F(o,1,k){
        sort(lsh[o].begin(),lsh[o].end());
        lsh[o].resize(unique(lsh[o].begin(),lsh[o].end())-lsh[o].begin());
        nb[o].init(lsh[o].size());
    }
    D(i,n,1)D(j,m,1){
        sum[i][j]+=sum[i][j+1]+sum[i+1][j]-sum[i+1][j+1];
        g[i][j]=!!sum[i][j];
        if(A[i]==B[j]){
            f[i][j]=Q(i,j,1,1);
            if((i||j)&&!f[i][j]){
                sum[i-1][j-1]++;
                if(lstA[i])sum[lstA[i]][j-1]--;
                if(lstB[j])sum[i-1][lstB[j]]--;
                if(lstA[i]&&lstB[j])sum[lstA[i]][lstB[j]]++;
            }
            for(auto[x,y,o]:qwq[i][j])
                Ans[o]=Q(i,j,x,y);
        }
        if(A[i]==B[j]&&g[i][j]){
            i64 l=lower_bound(lsh[A[i]].begin(),lsh[A[i]].end(),pA[i]-(pB[j]+lB[j]-1))-lsh[A[i]].begin();
            i64 r=upper_bound(lsh[A[i]].begin(),lsh[A[i]].end(),pA[i]+lA[i]-1-pB[j])-lsh[A[i]].begin()-1;
            nb[A[i]].chg(l,r,make_pair(i,j));
        }
    }
    F(o,1,q)puts(Ans[o]?"Yes":"No");
    return 0;
}