题解：P11831 [省选联考 2025] 追忆

· · 题解

解法

首先发现 a 和 b 的范围都不超过 n，非常果断地对 a 和 b 的值域分块，分别维护每个值在序列中的出现位置。这样就能做到 O(1) 修改了。

接着看询问操作，维护一个点集 S 表示能够成为答案的点。

为了保证 l \leq a_y \leq r，先将满足条件的点通过分块 O(n) 加入点集，再考虑可达性。 这个可达性目前最优秀的做法是用 bitset 优化 O(\frac{n^2}{w}) 算出来。

等等？bitset？忽然想到，我们之前的分块操作以及计算答案的做法都可以用 bitset 优化，于是我们询问操作计算 l \leq a_y \leq r 的点的步骤的时间优化成了 O(\frac{n}{\sqrt w})。

接下来就简单了，我们枚举答案所在的块，然后 O(\frac{n}{w}) 的时间检验，最后在块内暴力算答案即可。

总时间复杂度为 O(\frac{nq}{\sqrt w})，块长实测后感觉 7000 跑得最快。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n' 
const int N=1e5+5,key=7000,sqN=120;
int n,m,q,tot,a[N],b[N],posa[N],posb[N];
int pos[N],lm[sqN],rm[sqN],op,x,y,l,r,res;
bitset<N> d[N],sa[sqN],sb[sqN],ans,emy;
vector<int> e[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;}
inline void slove(){
    n=read(),m=read(),q=read(),tot=(n-1)/key+1;
    for(int i=1;i<=n;i++) pos[i]=(i-1)/key+1,e[i].clear();
    for(int i=1;i<=tot;i++) lm[i]=rm[i-1]+1,rm[i]=min(n,i*key),sa[i]=sb[i]=emy;
    for(int i=1,u,v;i<=m;i++) u=read(),v=read(),e[u].push_back(v);
    for(int i=n;i>=1;i--){ d[i]=emy,d[i][i]=1; for(int v:e[i]) d[i]|=d[v];}
    for(int i=1;i<=n;i++) a[i]=read(),posa[a[i]]=i,sa[pos[a[i]]][i]=1;
    for(int i=1;i<=n;i++) b[i]=read(),posb[b[i]]=i,sb[pos[b[i]]][i]=1;
    for(;q--;){ op=read();
        if(op==1){ x=read(),y=read();
            sa[pos[a[x]]][x]=sa[pos[a[y]]][y]=0,
            swap(a[x],a[y]),posa[a[x]]=x,posa[a[y]]=y,
            sa[pos[a[x]]][x]=sa[pos[a[y]]][y]=1;}
        else if(op==2){ x=read(),y=read();
            sb[pos[b[x]]][x]=sb[pos[b[y]]][y]=0,
            swap(b[x],b[y]),posb[b[x]]=x,posb[b[y]]=y,
            sb[pos[b[x]]][x]=sb[pos[b[y]]][y]=1;}
        else if(op==3){ x=read(),l=read(),r=read(),res=0,ans=emy;
            if(pos[l]==pos[r]) for(int i=l;i<=r;i++) ans[posa[i]]=1;
            else{ for(int i=l;i<=rm[pos[l]];i++) ans[posa[i]]=1;
                for(int i=lm[pos[r]];i<=r;i++) ans[posa[i]]=1;
                for(int i=pos[l]+1;i<=pos[r]-1;i++) ans|=sa[i];
            } ans&=d[x];for(int i=tot;i>=1;i--)
                if((sb[i]&ans).any()){res=i;break;}
            if(!res){cout<<0<<endl;continue;}
            for(int i=rm[res];i>=lm[res];i--)
                if(ans[posb[i]]) {cout<<i<<endl;break;}
        }
    }
}
int main(){
    for(int c=read(),t=read();t--;) slove();
    return 0;
}

希望能对大家有所帮助。