题解：P11831 [省选联考 2025] 追忆（民间数据）

· · 题解

前言

考场上想到了一个复杂度很不优秀的做法，觉得过不了，没打完就弃了。现在打了一下发现能过洛谷全部民间数据。悲。

做法

我的做法时间复杂度是 O(nq)，但是会乘上 \frac{1}{\sqrt{w}} 的常数。卡过了所有民间数据，不保证官方数据能过。

首先我们用bitset存一下每个点能到达的点的编号的集合，然后再开两个分块 bitset 数组分别存储一下每个 a_i 和 b_i 在某个范围 B 内的 i 的集合。

对于两类修改，可以非常轻松地 O(1) 改掉。

而对于询问来说，我们先从高到低枚举答案在哪个块里，然后再枚举答案在这个块里的哪里。不规范地表述一下，单次查询复杂度 O(\frac{n^2}{wB}+B)，所以 B 取 \frac{n}{\sqrt{w}} 最优。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int blen=sqrt((long long)N*(long long)N/64)+2;
bitset<N>s[N],clr,sa[114],sb[114],fd;
int bnum;
int a[N],b[N],pa[N],pb[N];
int n,m,q;
int bel[N],belL[N],belR[N],blL[114],blR[114];
vector<int>e[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int kkksc03,T;
    cin>>kkksc03>>T;
    while(T--){
        cin>>n>>m>>q;
        bnum=(n-1)/blen+1;
        for(int i=1;i<=n;i++)bel[i]=(i-1)/blen+1;
        for(int i=1;i<=bnum;i++)blL[i]=blR[i-1]+1,blR[i]=blen*i;
        blR[bnum]=n;
        for(int i=1;i<=n;i++)belL[i]=blL[bel[i]],belR[i]=blR[bel[i]];
        for(int i=1;i<=n;i++)e[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;cin>>u>>v;
            e[u].push_back(v);
        }
        for(int i=1;i<=bnum;i++){
            sa[i]=sb[i]=clr;
        }
        for(int x=n;x>=1;x--){
            s[x]=clr;
            s[x].set(x,1);
            for(int y:e[x]){
                s[x]|=s[y];
            }
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
            pa[a[i]]=i;
            sa[bel[a[i]]].set(i,1);
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
            pb[b[i]]=i;
            sb[bel[b[i]]].set(i,1);
        }
        while(q--){
            int op;cin>>op;
            if(op==1){
                int x,y;
                cin>>x>>y;
                sa[bel[a[x]]].set(x,0);
                sa[bel[a[y]]].set(y,0);
                swap(a[x],a[y]);
                pa[a[x]]=x;pa[a[y]]=y;
                sa[bel[a[x]]].set(x,1);
                sa[bel[a[y]]].set(y,1);
            }
            if(op==2){
                int x,y;
                cin>>x>>y;
                sb[bel[b[x]]].set(x,0);
                sb[bel[b[y]]].set(y,0);
                swap(b[x],b[y]);
                pb[b[x]]=x;pb[b[y]]=y;
                sb[bel[b[x]]].set(x,1);
                sb[bel[b[y]]].set(y,1);
            }
            if(op==3){
                int x,l,r;
                cin>>x>>l>>r;
                int pos=0,ans=0;
                fd=clr;
                if(bel[l]==bel[r]){
                    for(int i=l;i<=r;i++)fd.set(pa[i],1);
                }
                else{
                    for(int i=l;i<=belR[l];i++)fd.set(pa[i],1);
                    for(int i=belL[r];i<=r;i++)fd.set(pa[i],1);
                    for(int i=bel[l]+1;i<=bel[r]-1;i++)fd|=sa[i];
                }
                fd&=s[x];
                for(int i=bnum;i>=1;i--){
                    if((sb[i]&fd).any()){
                        pos=i;
                        break;
                    }
                }
                if(!pos){
                    cout<<0<<"\n";
                    continue;
                }
                for(int i=blR[pos];i>=blL[pos];i--){
                    if(fd[pb[i]]){
                        ans=i;
                        break;
                    }
                }
                cout<<ans<<"\n";
            }
        }
    }
    return 0;
}

我考场但凡打一下呢……