[省选联考 2025] 追忆 题解

· · 题解

思路可以见游记。

这是一个很暴力的考场做法，似乎没看见跟我一样的。

首先有向图可达性算是比较典的 O(\frac{n^2}{\omega})，正好题目也提示了我们空间和时间都很大，所以这个肯定对完了。具体地，预处理 n 个 bitset C_{i} 表示 i 是否可达 j。查询的时候相当于查询 f_i 中所有 a 在值域中的 b 的最大值。

然后这两个带修看上去都非常不容易，好像只会 ABC 性质但是又没有。考察思考的方向，注意到如果 i 可达集合是 [i,n] 所有点的话不弱于动态二维数点，而这个题已经有一个平方级别的暴力部分了所以不妨完全放弃 polylog 开始想分块之类的暴力结构。

尝试解决 a 上的值域限制。一个基于 a 静态的想法是，处理 a 的每个值域前缀对应的下标和。即 A_i 表示所有 a_j\le i 的 j 的集合组成的 bitset。这样至少可以在每次询问中 O(\frac n\omega) 地去除 a 的限制，似乎是不错的。再仔细一想，这个空间似乎已经是两倍的 \frac{n^2}{\omega}，一定会很卡，所以考虑放弃。

这种前缀和相关的题需要注意到，如果查询的复杂度和预处理的复杂度很不平衡，可以套用一些看上去几乎无意义的分块来压缩空间（有一个较深的印象是我和 irris 的这个题的这篇题解）。注意到我们分块之后，查询的时候的单点修改的复杂度是非常小的，是小常数 O(1)，然而查询整块非常耗费时间。而我们非常经得起大量的散块查询，在 n\le 10^5 的时候把块长开到 2000 都可以接受。于是可以细想分块了！

不妨按 B 分块。说人话就是只维护所有 i\equiv 0(\bmod B) 的 i 的 A_i。这样还有一个好处是，对 a 的单点修改只会改到 \frac{n}{B} 个 A_i，所以 op=1 也可以接受了。查询的时候相当于需要支持查询单点 A_r，可以先调用 A_{B\lfloor\frac{r}{B}\rfloor}，再把缺的单点部分暴力补上。这整个部分时间复杂度是 O(\frac{n^2}{\omega}+q(B+\frac{n}{\omega}+\frac nB))。

实际上这个时候写一个取出所有符合要求的点求 b_{\max} 可以在最后一个大样例跑 7s，几乎可以通过了。

然后考虑如何优化 b 的部分。可以发现即使是静态问题都没有什么优秀的做法。直接枚举或者直接分块显然没有什么理论低于 O(nq) 的做法。

考虑为什么要我们求 b_{\max} 呢？有一个直接的想法是二分答案，变成判定给定 bitset 和 b 的值域区间是否有交。不妨把 b 的值域取反变成前缀（方便我自己理解），类似上面地设计 D_{i} 表示所有 b_j\le i 的 j 组成的 bitset（这里似乎和块长的字母重复了，那就随便新取一个）。在不带修的时候可以做到 O(\frac{nq}{\omega}\log n)。感觉很蠢，还不能带修。但是 b 的修改是否可以参考 a 的修改呢？

这就不得不提到 WC 文艺汇演的相声（这句话也给了我相当的启发）：

找一个数在有序序列中的出现位置的时候，先分块！二分它在哪个块里，然后在块里二分！就做到了 O(\log\sqrt n)！

可以想到仍然对 b_i 分块，维护方法同 a_i。查询的时候直接二分它在哪个块里（因为只维护了整块信息，查询还方便），然后暴力查询块内，这样完美平衡了一下单点查询的 O(1) 和整块前缀查询的 O(\frac n\omega)！

具体地，维护所有整块代表的 bitset 的前缀和。查询的时候在大块上查询，可以极大的削掉 \log n 的部分。check 的时候只需要拿 D_{iB} 和当前询问的 bitset 判断交是否非空即可。对于散块，暴力查询的 O(1) 还是很可观的！同时分块仍然可以支持带修！这部分时间复杂度 O(q(\frac{n\log{\frac nB}}{\omega}+B+\frac{n}{B}))。具体 B 取啥的时候最优懒得算了，反正我直接取 B=2000 在大样例跑了 2.3s。此时 \log \frac nB 只有 6，至少少了三倍常数。上下取同一个 B，总时间复杂度就是 O(\frac{n^2}{\omega}+q(\frac{n\log{\frac nB}}{\omega}+B+\frac{n}{B}))。

建议手写 bitset，理由不知道。

考场代码：

#include<bits/stdc++.h>
#define MOD 998244353
#define int long long
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pii pair<int,int>
#define pb push_back
#define all(v) v.begin(),v.end()
#define over {cout<<x<<"\n";return;}
using namespace std;
int read(){
    int res=0;char c=getchar();
    while(c<48||c>57)c=getchar();
    do res=(res<<1)+(res<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
    return res;
}
int qpow(int a,int b,int m=MOD){
    int res=1;
    while(b)res=b&1? res*a%m:res,a=a*a%m,b>>=1;
    return res;
}
#define ui unsigned int
int ID;
vector<int>v[100005];
int n,m,q,BL,CL;
ui C[100000][1563];
ui A[400][1563];
ui B[400][1563];
int a[100000],b[100000],ia[100000],ib[100000];
ui qr[1563];
void updA(int x,int y){
    REP(i,x/BL,CL)A[i][y>>6]^=1ull<<(y&63);
}
void updB(int x,int y){
    REP(i,x/BL,CL)B[i][y>>6]^=1ull<<(y&63);
}
void opA(int x){
    int d=x/BL-1;
    if(x>=BL){
        REP(j,0,m)qr[j]^=A[d][j];
    }
    REP(i,x/BL*BL,x+1)qr[ia[i]>>6]^=1ull<<(ia[i]&63);
}
void Main(){
    n=read();m=read();q=read();
    REP(i,0,n)v[i].clear();
    REP(i,0,m){
        int x,y;
        x=read()-1;y=read()-1;
        v[x].pb(y);
    }
    m=(n-1)>>6;++m;
    for(int i=n-1;i>=0;--i){
        REP(j,i>>6,m)C[i][j]=0;
        C[i][(i>>6)]=1ull<<(i&63);
        for(auto j:v[i]){
            REP(l,j>>6,m)C[i][l]|=C[j][l];
        }
    }
    BL=sqrt(n*7);BL=min(BL,n);
    BL=min(2000ll,n);
    CL=(n-1)/BL+1;
    REP(i,0,n){
        a[i]=read()-1;
        ia[a[i]]=i;
    }
    REP(i,0,n){
        int d=i/BL;
        if(i%BL==0){
            if(i){
                REP(j,0,m)A[d][j]=A[d-1][j];
            }else{
                REP(j,0,m)A[d][j]=0;
            }
        }
        A[d][ia[i]>>6]|=1ull<<(ia[i]&63);
    }
    REP(i,0,n)b[i]=n-read(),ib[b[i]]=i;
    REP(i,0,n){
        int d=i/BL;
        if(i%BL==0){
            if(i){
                REP(j,0,m)B[d][j]=B[d-1][j];
            }else{
                REP(j,0,m)B[d][j]=0;
            }
        }
        B[d][ib[i]>>6]|=1ull<<(ib[i]&63);
    }
    REP(i,0,q){
        int op,x,y,l,r;
        op=read();
        if(op==1){
            x=read()-1;y=read()-1;
            swap(a[x],a[y]);
            x=a[x];y=a[y];
            updA(x,ia[x]);updA(x,ia[y]);
            updA(y,ia[y]);updA(y,ia[x]);
            swap(ia[x],ia[y]);
        }else if(op==3){
            x=read()-1;l=read()-1;r=read()-1;
            REP(j,0,m)qr[j]=0;
            if(l)opA(l-1);
            opA(r);
            REP(j,0,m)qr[j]&=C[x][j];
            int ans=0,fl=0;
            REP(j,0,m){
                if(qr[j])fl=1;
            }
            if(!fl){
                cout<<0<<'\n';
                continue;
            }
            int l=0,r=CL-1,res=r;
            while(l<=r){
                int mid=(l+r)>>1,f=0;
                REP(j,0,m)if(B[mid][j]&qr[j]){f=1;break;}
                if(f)res=mid,r=mid-1;
                else l=mid+1;
            }
            for(int i=res*BL;i<n;++i){
                int x=ib[i];
                if(qr[x>>6]&(1ull<<(x&63))){
                    ans=i;
                    break;
                }
            }
            cout<<n-ans<<'\n';
        }else{
            x=read()-1;y=read()-1;
            swap(b[x],b[y]);
            x=b[x];y=b[y];
            updB(x,ib[x]);updB(x,ib[y]);
            updB(y,ib[y]);updB(y,ib[x]);
            swap(ib[x],ib[y]);
        }
    }
}
signed main(){
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    int tc=1;
    ID=read();tc=read();
    while(tc--)Main();
    return 0;
}