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

· · 题解

前言

第一次正赛场切黑题。省选续命成功了（虽然 Day 2 爆了但是肯定能进队对吧），希望最后四个月的 OI 生涯能让这第一次不是最后一次。

题解

下文分析认为 n,q 同阶。实际实现时有些块长需要根据 n,q 修改。

和有向图可达性相关了，结合 6s 2048MB 的时空限制，倾向于思考 \mathcal O(\frac{n^2}{w}) 的做法。

那么我们每次查询时要做的事情大致可以分为三部分：

一步一步来做。

Part 1

这部分是经典的：对于每个节点 u，我们预处理出一个 bitset b_u 表示 u 可达点的集合。按照拓扑序倒序（本题中可以直接 n\to 1）递推即可做到 \mathcal O(\frac{n^2}{w})。

查询的时候直接调用 b_x。

Part 2

这部分需要做区间查询。我们发现，bitset 的查询可以用 ST 表处理，因为重合的部分可以并起来，不会多算。因此我们可以考虑用 ST 表处理。

但是这样预处理的时空复杂度就已经来到了 \mathcal O(\frac{n^2\log n}{w})，更不用说修改了。这里我赛时想到的处理方式是：按照 B_1 大小分块，对于每个块，处理 all_i 表示这块内所有 bitset 的并，并建立 all 序列上的 ST 表。查询的时候整块直接调用 ST 表，散块暴力插入。

这样做的时间复杂度是 \mathcal O(\frac{n^2\log {\frac{n}{B_1}}}{wB_1})。我取了 B_1=\frac{n}{128}。

至于修改，再套一层定期重构就行了。每 B_2 次询问就重构一次，查询的时候，在基础查询的基础上，重新判断在上次重构之后被修改的那些 a_i 是否在范围内。时间复杂度 \mathcal O(\frac{n^3\log {\frac{n}{B_1}}}{wB_1B_2}+nB_2)。我取了 B_2=\frac{n}{64}。

Part 3

这部分需要查询一个集合中的最大值。由于 a,b 都是乱序的，我们不能直接用 _Find_first() 直接找到最大值。

这里我赛时想到的方法是：对 b 序列分块，以 B_3 为块长，预处理出 b_i 在 [n-B_3+1,n],[n-2B_3+1,n],[n-3B_3+1,n],\dots,[1,n] 中对应的 i 的集合。这样查询的时候，我们可以二分一个长度为 B_3 的倍数的后缀，看是否有交。这样就可以把答案定位到一个长度为 B_3 的区间里，再暴力扫描就行了。

修改是非常容易的，直接枚举后缀就行了，复杂度只有 \mathcal O(\frac{n^2}{B_3})。

复杂度 \mathcal O(\frac{n^2\log {\frac{n}{B_3}}}{w}+nB_3)。我取了 B_3=\frac{n}{16}。

至此整题已被解决，常数非常小，洛谷 5s 通过。

其实这里每个块长大概要取什么是容易平衡出来的，都应该是 \frac{n}{w} 状物，但是由于有些部分常数更大，所以需要微调。

#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e5+9,M=2e5+9;
ll typ,T,n,m,q,U[M],V[M];
ll a[N],b[N],ord_a[N],ord_b[N];
ll stk[N*2],top;
bitset<N>go[N];
bitset<N>st[9][135];
bitset<N>btb[50],tmp;
ll lg[150],S,L[N],R[N],bel[N];
ll b_S,blb[N];
void First_Build(){
    S=min(n,(n+127)/128);
    rep(i,0,n+1)L[i]=R[i]=bel[i]=0;
    rep(i,1,n){
        bel[i]=(i-1)/S+1;
        if(!L[bel[i]])L[bel[i]]=i;
        R[bel[i]]=i;
    }
    b_S=max(1,n/16);
    rep(i,1,n)blb[i]=(i-1)/b_S+1;
    rep(i,0,blb[n]+1)btb[i].reset();
    rep(i,1,n){
        rep(j,1,blb[i])btb[j].set(ord_b[i]);
    }
}
void Rebuild(){
    top=0;
    rep(i,1,n)ord_a[a[i]]=i;
    rep(i,1,bel[n])st[0][i].reset();
    rep(i,1,bel[n]){
        rep(j,L[i],R[i])st[0][i].set(ord_a[j]);
    }
    rep(k,1,lg[bel[n]]){
        rep(i,1,bel[n]-(1<<k)+1){
            st[k][i]=st[k-1][i]|st[k-1][i+(1<<(k-1))];
        }
    }
}
void Query_st(ll l,ll r,bitset<N>&ans){
    ll p=lg[r-l+1];
    ans|=st[p][l]|st[p][r-(1<<p)+1];
}
void Query(ll l,ll r,bitset<N>&ans){
    ll bl=bel[l],br=bel[r];
    if(bl==br){
        rep(i,l,r)ans.set(ord_a[i]);
        return ;
    }
    rep(i,l,R[bl])ans.set(ord_a[i]);
    rep(i,L[br],r)ans.set(ord_a[i]);
    if(bl+1<=br-1)Query_st(bl+1,br-1,ans);
}
vector<ll>to[N];
void solve(){
    n=read(),m=read(),q=read();
    rep(i,1,m)U[i]=read(),V[i]=read();
    rep(i,0,n+1)to[i].clear();
    rep(i,1,m)to[U[i]].push_back(V[i]);
    rep(i,1,n)a[i]=read();
    rep(i,1,n)b[i]=read(),ord_b[b[i]]=i;
    rep(i,0,n+1)go[i].reset();
    rep(i,1,n)go[i].set(i);
    per(i,n,1){
        for(ll j:to[i])go[i]|=go[j];
    }
    ll rebuild_lim=max(1,q/64); // lim can't be 0
    First_Build(),Rebuild();
    top=0;
    ll C1=0,C2=0,C3=0;
    rep(i,1,q){
        ll op=read();
        // cout<<"going: "<<i<<" "<<op<<endl;
        if(op==1){
            C1++;
            ll x=read(),y=read();
            stk[++top]=x,stk[++top]=y;
            swap(ord_a[a[x]],ord_a[a[y]]);
            swap(a[x],a[y]);
        }
        else if(op==2){
            C2++;
            ll x=read(),y=read();
            ll frm=blb[b[x]],to=blb[b[y]];
            if(frm<to){
                rep(i,frm+1,to)btb[i].set(x);
            }
            else if(frm>to){
                rep(i,to+1,frm)btb[i].reset(x);
            }
            swap(frm,to);
            if(frm<to){
                rep(i,frm+1,to)btb[i].set(y);
            }
            else if(frm>to){
                rep(i,to+1,frm)btb[i].reset(y);
            }
            swap(ord_b[b[x]],ord_b[b[y]]);
            swap(b[x],b[y]);
        }
        else {
            C3++;
            ll x=read(),l=read(),r=read();
            tmp.reset();
            Query(l,r,tmp);
            rep(j,1,top){
                ll x=stk[j];
                if(a[x]<l||a[x]>r)tmp.reset(x);
                else tmp.set(x);
            }
            // rep(j,1,n)cout<<tmp[j];
            // cout<<endl;
            tmp&=go[x];
            ll ql=1,qr=blb[n],pos=0;
            while(ql<=qr){
                ll mid=(ql+qr)>>1;
                if((btb[mid]&tmp).any())pos=mid,ql=mid+1;
                else qr=mid-1;
            }
            if(!pos){
                write(0),putchar('\n');
                goto bed;
            }
            per(j,min(n,pos*b_S),(pos-1)*b_S+1){
                ll x=ord_b[j];
                if(tmp[x]){
                    write(j),putchar('\n');
                    goto bed;
                }
            }
        }
        bed:
        if(i%rebuild_lim==0)Rebuild();
    }
    // cerr<<C1<<" "<<C2<<" "<<C3<<"\n";
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    freopen("recall.in","r",stdin);
    freopen("recall.out","w",stdout);
    typ=read(),T=read();
    rep(i,2,128)lg[i]=lg[i>>1]+1;
    while(T--)solve();
    cerr<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}

/*
g++ -std=c++14 -O2 -Wall -Wextra recall.cpp -o recall && ./recall
*/