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

王熙文 · 2025-05-26 19:34:38 · 题解

看游记发现很多人提到了这道题 \mathcal O(nq) 得了 88 及以上的分数，但是题解区没有人传授卡常技巧，于是我来发一篇。这是一个非常好写的 \mathcal O(nq) 的做法，洛谷最大点 4.62s。

思路

省流：将可达性改为一个点可以到达的所有 b 的值，手写 bitset 可以做到找到即 break、访问连续和只访问 1 的位置三个优秀的性质。对于二操作可以可以先将要修改的位置存下来，在三操作的时候再修改，这样就能过了。

首先 DAG 可达性问题显然要使用 bitset。具体的，对每个点记录 \text{bit}_{i,j} 表示 i 是否可以到达 j。从 n 到 1 遍历每个点，并将 \text{bit}_i 或上 i 的出边的 \text{bit} 即可。

发现如果从大到小枚举 b_y，如果满足条件了就可以 break，跑不满。但是此时 \text{bit} 数组的访问会不连续，不行。

考虑将 \text{bit}_{i,j} 改为 i 是否可以到达 b_k=j 的 k。这样数组访问就连续了。而且更好的一点是，如果手写 bitset，可以只遍历到值为 1 的位置。具体的，对于一个 unsigned long long 类型的数，可以调用 __lg(x) 得到最高位，再让 x 减去 1llu<<__lg(x)。__lg() 函数的速度是非常快的。

但是此时交换 b_x,b_y 的时候会影响 \text{bit}（对于所有 \text{bit}_i，交换 b_x 和 b_y 位置上的值）。发现三操作只会访问一个 \text{bit}_i，所以可以将修改存下来，并记录 pos_i 表示 \text{bit}_i 此时修改到了修改序列上的哪个位置，三操作的时候将未修改的部分更新即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> e[100010];
int a[100010],b[100010];
unsigned long long bit[100010][(int)1e5/64+10];
int wz1[100010],wz2[100010];
int tot,xx[100010],yy[100010];
int pos[100010];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int testid,t; cin>>testid>>t; while(t--)
    {
        cin>>n>>m>>q;
        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<=n; ++i) cin>>a[i];
        for(int i=1; i<=n; ++i) cin>>b[i],wz1[b[i]]=i,wz2[b[i]]=a[i];
        for(int i=n; i>=1; --i)
        {
            memset(bit[i],0,sizeof(bit[i]));
            bit[i][b[i]>>6]=(1llu<<(b[i]&63));
            for(int j:e[i])
            {
                for(int k=0; k<=(n>>6); ++k) bit[i][k]|=bit[j][k];
            }
        }
        tot=0;
        for(int i=1; i<=n; ++i) pos[i]=1;
        while(q--)
        {
            int op,x,y,l,r; cin>>op;
            if(op==1)
            {
                cin>>x>>y;
                swap(wz2[b[x]],wz2[b[y]]);
            }
            if(op==2)
            {
                cin>>x>>y;
                swap(wz1[b[x]],wz1[b[y]]);
                swap(wz2[b[x]],wz2[b[y]]);
                xx[++tot]=b[x],yy[tot]=b[y];
                swap(b[x],b[y]);
            }
            if(op==3)
            {
                cin>>x>>l>>r;
                while(pos[x]<=tot)
                {
                    int a=(bit[x][xx[pos[x]]>>6]>>(xx[pos[x]]&63)&1);
                    int b=(bit[x][yy[pos[x]]>>6]>>(yy[pos[x]]&63)&1);
                    if(a!=b)
                    {
                        if(a==0)
                        {
                            bit[x][xx[pos[x]]>>6]+=(1llu<<(xx[pos[x]]&63));
                            bit[x][yy[pos[x]]>>6]-=(1llu<<(yy[pos[x]]&63));
                        }
                        else
                        {

                            bit[x][xx[pos[x]]>>6]-=(1llu<<(xx[pos[x]]&63));
                            bit[x][yy[pos[x]]>>6]+=(1llu<<(yy[pos[x]]&63));
                        }
                    }
                    ++pos[x];
                }
                bool flag=0;
                for(int j=(n>>6); j>=0 && !flag; --j)
                {
                    if(bit[x][j]==0) continue;
                    unsigned long long now=bit[x][j];
                    while(now!=0)
                    {
                        int wz=(j<<6)+__lg(now);
                        if(l<=wz2[wz] && wz2[wz]<=r)
                        {
                            cout<<wz<<'\n';
                            flag=1;
                            break;
                        }
                        now-=(1llu<<__lg(now));
                    }
                }
                if(!flag) cout<<0<<'\n';
            }
        }
    }
    return 0;
}