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

· · 题解

介绍一个坨的算法，，

注意到空间很大，时间很大，dag，所以 bitset 逃不开了。

又注意到每次询问两个条件互不干扰，考虑每个单独求满足条件的点再求两者交，最后再处理最大值。所以接下来的部分都是离线处理。

对于条件二，直接求可达性即可，这一部分 O(\frac{n^2}{w})。

对于条件一，可以改为求 a_i\le r 的点集合去掉 a_i < l 的点集合。扫一遍操作序列，维护一个序列 c，满足处理完之前的操作后 a_{c_i}=i，那么现在就要能做到求出一个 c 的前缀的点的集合。这一坨我只会用树状数组加上 bitset 维护，复杂度 O(\frac{n^2\log n}{w})。

求出来哪些点满足条件后现在要求最大值，这一部分可以参考对条件一的处理方法。同样维护序列 c，只不过这次条件换成 b_{c_i}=i，每次二分最大值，看后缀是否和满足条件的点有交即可。使用树状数组二分，复杂度可做到 O(\frac{n^2 \log n}{w})，但是常数比较大。

总复杂度 O(\frac{n^2 \log n}{w})，时间稳定，极限卡常能搞到 88 分。

说下关于空间的，对于 n\le 8\times 10^4 的部分，开两个二维 bitset，一个用来计算，另一个存结果即可。对于最后一个 subtask，存结果的只开一半，一次处理一半的询问就行，但是跑太慢过不了。

赛时 STL 版本要跑 10s，最后手写 bitset 挂了只能交破烂 STL 版本的 bitset 上去，于是特殊性质全没动，也没进一步优化，遗憾离场，，，

（剩下部分是赛后的）

注意到树状数组查询时到一些节点时其集合包含的元素不多，但合并还是 O(\frac n w)，二分也同理。于是设置一个阈值 B，对于第二部分当节点代表区间长度小于 B 时直接暴力合并，第三部分二分时节点长度小于 B 直接判交，可以优化到 O(\frac{n^2\log w}{w})，还能剔除掉一些节点优化空间，至此可以通过。

但是正解懒得写了，赛后 88 分代码：

#include<bits/stdc++.h>
using namespace std;
const int MaxN=80000;
int C,n,m,q,a[MaxN+1],b[MaxN+1];
struct Bitset{
    static const int Size=MaxN/64+1;
    unsigned long long arr[Size];
    Bitset(){clear();}
    int count()const{
        for(int i=0;i<Size;i++)if(arr[i])return 1;
        return 0;
    }
    void clear(){
        for(int i=0;i<Size;i++)arr[i]=0;
    }
    bool spfunc1(const Bitset&b)const{
        for(int i=0;i<Size;i++)if(arr[i]&b.arr[i])return true;
        return false;
    }
    void rev(int x){arr[x/64]^=(1ull<<(x%64));}
    void set(int x,bool b){if(((arr[x/64]>>(x%64))&1)!=b)arr[x/64]^=(1ull<<(x%64));}
    Bitset&operator&=(const Bitset&b){
        for(int i=0;i<Size;i++)arr[i]&=b.arr[i];
        return *this;
    }
    Bitset&operator|=(const Bitset&b){
        for(int i=0;i<Size;i++)arr[i]|=b.arr[i];
        return *this;
    }
    Bitset&operator^=(const Bitset&b){
        for(int i=0;i<Size;i++)arr[i]^=b.arr[i];
        return *this;
    }
    Bitset operator&(const Bitset&b)const{return Bitset(*this)&=b;}
    Bitset operator^(const Bitset&b)const{return Bitset(*this)^=b;}
}bt[MaxN+1],rs[MaxN+1];
vector<int>g[MaxN+1];
bool vst[MaxN+1];
int que[MaxN+1][4];
int LowBit(int x){return(x)&(-x);}
void Modify(int u,int x,int y){for(;u<=n;u+=LowBit(u))bt[u].rev(x),bt[u].rev(y);}
void Modifyo(int u,int x){for(;u<=n;u+=LowBit(u))bt[u].rev(x);}
Bitset Ask(int u){
    Bitset res;
    for(;u;u-=LowBit(u))res|=bt[u];
    return res;
}
void DFS(int u){
    if(vst[u])return;
    vst[u]=true;
    bt[u].set(u,true);
    for(int v:g[u])DFS(v),bt[u]|=bt[v];
}
int Check(int x){
    if(!rs[x].count())return 0;
    int p=__lg(n),u=(1<<p),ans=INT_MAX;
    while(p>=0){
        if(bt[u].spfunc1(rs[x])){
            ans=min(ans,u);
            u^=(1<<p);
        }
        if(p==0)return n-ans+1;
        do{p--;}while((u^(1<<p))>n);
        u^=(1<<p);
    }
    return n-ans+1;
}
void Solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)g[i].clear();
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)bt[i].clear();
    for(int i=1;i<=q;i++){
        cin>>que[i][0]>>que[i][1]>>que[i][2];
        if(que[i][0]==3)cin>>que[i][3];
    }
    for(int i=1;i<=n;i++)Modifyo(a[i],i);
    for(int i=1,c=0;i<=q;i++){
        if(que[i][0]==1){
            int x=que[i][1],y=que[i][2];
            Modify(a[x],x,y);
            Modify(a[y],x,y);
            swap(a[x],a[y]);
        }
        if(que[i][0]==3){
            ++c;
            rs[c]=Ask(que[i][3])^Ask(que[i][2]-1);
        }
    }
    for(int i=1;i<=n;i++)vst[i]=false,bt[i].clear();
    for(int i=1;i<=n;i++)DFS(i);
    for(int i=1,c=0;i<=q;i++){
        if(que[i][0]==3){
            ++c;
            rs[c]&=bt[que[i][1]];
        }
    }
    for(int i=1;i<=n;i++)bt[i].clear();
    for(int i=1;i<=n;i++)Modifyo(n-b[i]+1,i);
    for(int i=1,c=0;i<=q;i++){
        if(que[i][0]==2){
            int x=que[i][1],y=que[i][2];
            Modify(n-b[x]+1,x,y);
            Modify(n-b[y]+1,x,y);
            swap(b[x],b[y]);
        }
        if(que[i][0]==3){
            ++c;
            cout<<Check(c)<<'\n';
        }
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    int T;
    cin>>C>>T;
    while(T--)
        Solve();
    return 0;
}