2021 2022 综合省选联考 2020 2025

省选联考记

WZH2026-06-282026-06-28

省选联考记

加油省选。

P7518 [省选联考 2021 A/B 卷] 宝石

这个算是一个比较基础的倍增题目了。

题目链接： [省选联考 2021 A/B 卷] 宝石。

题目内容:

给一颗树，树上每个点有点权。

每次求序列 $P_1,P_2,...P_c$ （ $c$ 为每次询问给的， $P$ 为预先定好的序列）是否是 $s$ 到 $t$ 路径上点权构成的序列的子序列。

$n,q \le 2\times 10^5$ 。

这个信息并不好维护。但是考虑到 $P$ 为定序列，我们可以预处理树上每个点 $i$ 往上走，跨越 $P$ 序列上 $2^j$ 个点后到达的点。

对于 $P$ 序列的正序和逆序都需要倍增存储。

这个东西是可以通过可持久化线段树维护的。

设正序倍增数组为 $up_{i,j}$ ，逆序为 $dn_{i,j}$ 。

那么首先我们求出 $s,t$ 的 $lca$ ，设为 $l$ 。

然后倍增跳跃，每次比较跳到的点和 $l$ 的深度，从而比较是否在 $s,t$ 路径上。

接下来用如出一辙的手段计算 $l,t$ 路径上的序列情况即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=200010,M=10000010;
int n,m,c,w[N],pw[N],rt[N],num[M],ls[M],rs[M],idx,up[N][20],dn[N][20],f[N][20],d[N],lg[N],Q;
vector<int>v[N];
void copy(int x,int y){num[x]=num[y],ls[x]=ls[y],rs[x]=rs[y];}
int insert(int p,int l,int r,int x,int y){
    ++idx,copy(idx,p);p=idx;
    if(l==r){
        num[p]=y;
        return p;
    }
    int mid=(l+r)>>1;
    if(mid>=x)ls[p]=insert(ls[p],l,mid,x,y);
    else rs[p]=insert(rs[p],mid+1,r,x,y);
    return p;
}
int query(int p,int l,int r,int x){
    if(l==r)return num[p];
    int mid=(l+r)>>1;
    return (mid>=x?query(ls[p],l,mid,x):query(rs[p],mid+1,r,x));
}
int build(int p,int l,int r){
    p=++idx;
    if(l==r)return p;
    int mid=(l+r)>>1;
    ls[p]=build(p,l,mid);
    rs[p]=build(p,mid+1,r);
    return p;
}
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    rt[x]=insert(rt[fa],1,c,w[x],x);
    f[x][0]=fa;
    up[x][0]=(w[x]==0||w[x]==c?-1:query(rt[x],1,c,w[x]+1));
    dn[x][0]=(w[x]==0||w[x]==1?-1:query(rt[x],1,c,w[x]-1));
    for(int i=1;i<=19;i++){
        f[x][i]=f[f[x][i-1]][i-1];
        if(up[x][i-1]!=-1)up[x][i]=up[up[x][i-1]][i-1];
        else up[x][i]=-1;
        if(dn[x][i-1]!=-1)dn[x][i]=dn[dn[x][i-1]][i-1];
        else dn[x][i]=-1;
    }
    for(int u:v[x])if(u!=fa)dfs(u,x);
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=f[x][lg[d[x]-d[y]]];
    if(x==y)return x;
    for(int i=19;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i],y=f[y][i];
        }
    }
    return f[x][0];
}
bool check(int st,int x,int y,int l){
    if(!x)return 1;
    y=query(rt[y],1,c,x);
    if(y!=-1&&d[y]>=d[l]){
        for(int i=19;i>=0;i--){
            if(dn[y][i]!=-1&&d[dn[y][i]]>=d[l]){
                y=dn[y][i];
            }
        }
        return w[y]<=st;
    } 
    return 0;
}
int main(){
    cin>>n>>m>>c;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1,x;i<=c;i++)cin>>x,pw[x]=i;
    for(int i=1;i<=n;i++)cin>>w[i],w[i]=pw[w[i]];
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    rt[0]=build(1,1,c);
    dfs(1,0);
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int x,y;
        cin>>x>>y;
        int l=lca(x,y),res=0;
        x=query(rt[x],1,c,1);
        if(x!=-1&&d[x]>=d[l]){
            for(int i=19;i>=0;i--){
                if(up[x][i]!=-1&&d[up[x][i]]>=d[l]){
                    x=up[x][i];
                }
            }
            res=w[x];
        }
        int L=res,R=c;
        while(L<R){
            int mid=(L+R+1)>>1;
            if(check(res+1,mid,y,l))L=mid;
            else R=mid-1;
        }
        cout<<L<<"\n";
    }
    return 0;
}

P6622 [省选联考 2020 A/B 卷] 信号传递

可以说， CSP-S2025 员工招聘和 IOI2002 任务安排我没有白写。我竟然也做出了这题。

题目链接： [省选联考 2020 A/B 卷] 信号传递。

题目内容：

一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,\dots,m$ ，相邻信号站之间相隔 $1$ 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 $1$ 单位时间。道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 $1$ 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗 $k$ 个单位时间。对于给定的长度为 $n$ 的信号传递序列 $S$ ，传递规则如下：

共 $n-1$ 次信号传递，第 $i$ 次信号传递将把信号从 $S_i$ 号信号站传递给 $S_{i+1}$ 号。

若 $S_{i+1}$ 号信号站在 $S_i$ 号右侧，则将使用普通传递方式，从 $S_i$ 号直接传递给 $S_{i+1}$ 号。

若 $S_{i+1}$ 号信号站在 $S_i$ 号左侧，则将使用特殊传递方式，信号将从 $S_i$ 号传递给控制塔，再由控制塔传递给 $S_{i+1}$ 号。

若 $S_i=S_{i+1}$ ，则信号无须传递。

阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后， $S$ 所消耗的传递时间最小能是多少。

$30\%$ 的数据： $m\leq 8, n\leq 100$ 。

$60\%$ 的数据： $m\leq 20$ 。

$70\%$ 的数据： $m\leq 21$ 。

$80\%$ 的数据： $m\leq 22$ 。

$100\%$ 的数据： $2\leq m\leq 23$ ， $2\leq n\leq 10^5$ ， $1\leq k\leq 100$ ， $1\leq S_i\leq m$ 。

时间限制 $3s$ ，空间限制 $512MB$ 。

容易看出这题是一个复杂度 $O(m2^m)$ 的状压。

先考虑朴素的状压 DP 。

设 $f_i$ 表示当前 $|i|$ 个信号站设置情况为 $i$ 时的最短时间。

对于 $f_i$ ，我们首先要枚举第 $|i|$ 个信号站 $j\in i$ 。

然后我们就需要算 $j$ 和前后信号站的时间消耗，进行转移。

设 $cnt_{i,j}$ 为从信号站 $i$ 到信号站 $j$ 的信号传递数量。

那么，对于每一个 $k\in i/\{j\}$ ，就需要使用特殊传递方法。此时的贡献必定为 $|i|+x$ 的形式。

但是有一个问题，就是状压中丢失了位置信息，导致 $x$ 无法计算，从而无法转移。

接下来就要用到 IOI2002 任务安排的 trick ：贡献提前计算。

我们在计算以前的贡献时，提前计算关于他们的贡献。

具体来说，枚举 $j$ 时，只计算 $j$ 到中转站的贡献，其余的不计算。

作为代价，还要枚举 $k\in U/i$ ，提前计算好所有 $k$ 到 $j$ 的要中转的贡献，提前加上 $|i|$ 。

然后就是 $j$ 到后面的贡献了。

这里我们面临了和之前一样的问题：无法确定后面数的位置。

并且这时不能再用 IOI 的那个方法解决了。

此时就有一个更为巧妙的想法：逐项递推。

具体的，不直接计算贡献，而是一个一个的递推贡献。每次对于 $p\in i ,q\in U/i$ ，计算 $p$ 到 $q$ 的传递次数，然后只递推一次贡献，即 $cnt_{p,q}$ 。

这个做法的正确性是显然的。

那么我们就写完了 $60$ 分了，因为这是一个 $2^mm^2$ 的算法。

容易看出复杂度瓶颈在枚举 $k$ ，这里我们可以 $O(m2^m)$ 预处理 $f_{i,j}=\displaystyle\sum_{k\in i}cnt_{k,j}$ 和 $F_{i,j}=\displaystyle\sum_{k\in i}cnt_{j,k}$ ，然后对原 DP 式子进行优化，这里比较简单。

但是这样为 MLE 。

此时还有一些巧妙的优化方法。

首先，可以预见的是 $f_{i,j},F_{i,j} <2^{16}$ ，也就是说可以用 unsigned short 存储。

然后，不难发现 $f_{i,j}$ 在 $j\in i$ 时无意义，所以可以省去一半空间。

最后就 AC 这题了。

$60$ 分 TLE 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=24,inf=0x3f3f3f3f;
int n,m,K,f[1<<M],s[N],cnt[M][M];
int bt(int i){return __builtin_popcount(i);}
int main(){
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=2;i<=n;i++)cnt[s[i-1]][s[i]]++;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<(1<<m);i++){
        int res2=0;
        for(int j=1;j<=m;j++){
            if((i>>j-1)&1^1)continue;
            for(int p=1;p<=m;p++){
                if((i>>p-1)&1)continue;
                res2+=cnt[j][p];
            }
        }
        for(int j=1;j<=m;j++){
            if((i>>j-1)&1^1)continue;
            if(f[i^(1<<j-1)]==inf)continue;
            int res=f[i^(1<<j-1)]+res2;
            for(int k=1;k<=m;k++){
                if(k==j)continue;
                if((i>>k-1)&1^1)continue;
                res+=cnt[j][k]*K*bt(i);
            }
            for(int k=1;k<=m;k++){
                if((i>>k-1)&1)continue;
                res+=cnt[k][j]*K*bt(i);
            }
            f[i]=min(f[i],res);
        }
   //     cout<<i<<" : "<<f[i]<<"\n";
    }
    cout<<f[(1<<m)-1];
    return 0;
}

$80$ 分 MLE 代码：

#include <bits/stdc++.h>
int Min(int a,int b){return a>b?b:a;}
using namespace std;
const int N=100000,M=23,inf=0x3f3f3f3f;
int n,m,K,f[1<<M],s[N],cnt[M][M];
int bt(int i){return __builtin_popcount(i);}
unsigned short g[M][1<<M],G[M][1<<M];
int main(){
    scanf("%d%d%d",&n,&m,&K);
    for(int i=0;i<n;i++)scanf("%d",s+i),s[i]--;
    for(int i=1;i<n;i++)cnt[s[i-1]][s[i]]++;
    for(int i=0;i<m;i++){
        for(int j=1;j<(1<<m);j++){
            int k=(j&-j);
            int p=__builtin_ctz(k);
            g[i][j]=g[i][j^k]+cnt[i][p];
            G[i][j]=G[i][j^k]+cnt[p][i];
        }
    }
    const int U=(1<<m)-1;
    for(int i=1;i<(1<<m);i++){
        int res2=0,Bt=bt(i),u=U^i;
        f[i]=inf;
        for(int j=0;j<m;j++){
            if((i>>j)&1^1)continue;
            res2+=g[j][u];
        }
        for(int j=0;j<m;j++){
            if((i>>j)&1^1)continue;
            int res=f[i^(1<<j)]+res2+g[j][i^(1<<j)]*K*Bt+G[j][u]*K*Bt;
            f[i]=Min(f[i],res);
        }
    }
    printf("%d",f[(1<<m)-1]);
    return 0;
}

$100$ 分 AC 代码：

#include <bits/stdc++.h>
int Min(int a,int b){return a>b?b:a;}
using namespace std;
const int N=100000,M=23,inf=0x3f3f3f3f;
int n,m,K,f[1<<M],s[N],cnt[M][M];
int bt(int i){return __builtin_popcount(i);}
unsigned short g[M][1<<M-1],G[M][1<<M-1];
int trans(int u,int j){
    int t1=(u&(1<<j)-1);
    int t2=((u>>j+1)<<j);
    return (t1|t2);
}
int main(){
    scanf("%d%d%d",&n,&m,&K);
    for(int i=0;i<n;i++)scanf("%d",s+i),s[i]--;
    for(int i=1;i<n;i++)cnt[s[i-1]][s[i]]++;
    for(int i=0;i<m;i++){
        for(int j=1;j<(1<<m-1);j++){
            int k=(j&-j);
            int p=__builtin_ctz(k);
            g[i][j]=g[i][j^k]+cnt[i][p+(p>=i)];
            G[i][j]=G[i][j^k]+cnt[p+(p>=i)][i];
        }
    }
    const int U=(1<<m)-1;
    for(int i=1;i<(1<<m);i++){
        int res2=0,Bt=bt(i);
        f[i]=inf;
        for(int j=0;j<m;j++){
            if((i>>j)&1^1)continue;
            res2+=g[j][trans(U^i,j)];
        }
        for(int j=0;j<m;j++){
            if((i>>j)&1^1)continue;
            int res=f[i^(1<<j)]+res2+g[j][trans(i^(1<<j),j)]*K*Bt+G[j][trans(U^i,j)]*K*Bt;
            f[i]=Min(f[i],res);
        }
    }
    printf("%d",f[(1<<m)-1]);
    return 0;
}

P6623 [省选联考 2020 A 卷] 树

神仙题目。

题目链接： P6623 [省选联考 2020 A 卷] 树。

题目内容：

给定一棵 $n$ 个结点的有根树 $T$ ，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$ 。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$ ，定义 $x$ 的价值为：
$val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))$
其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数， $d(x, x) = 0$ 。 $\oplus$ 表示异或运算。

请你求出 $ \displaystyle \sum_{i=1}^n val(i)$ 的结果。

对于 $10\%$ 的数据： $1\leq n\leq 2501$ ；

对于 $40\%$ 的数据： $1\leq n\leq 152501$ ；

另有 $20\%$ 的数据：所有 $p_i=i-1$ （ $2\leq i\leq n$ ）；

另有 $20\%$ 的数据：所有 $v_i=1$ （ $1\leq i\leq n$ ）；

对于 $100\%$ 的数据： $1\leq n,v_i \leq 525010$ ， $1\leq p_i\leq n$ 。

首先看到异或就应该想到按位拆贡献。

尝试计算二进制第 $i$ 位的贡献。

直接算行不太通，可以转化成为某一个点 $x$ 对其祖先节点的贡献。

容易发现，假设 $v_x=0$ ，那么对于 $x$ 的祖先的第 $i$ 位的贡献一定是一段循环的 $01$ 序列。

若 $v_x\ne 0$ ，贡献也是一段有头的循环节，计算这个较为简单。

然后就是要对祖先经行第 $i$ 位的贡献累加了。可以发现 $x$ 对祖先 $d$ 的贡献由 $d$ 的深度决定（因为循环节）。

那么我们可以对处于循环节同一位置的数的贡献累加相同值，也就是压缩，这个在 CSP-J2023 旅游巴士中也有所体现。

设 $w_{i,j}$ 为二进制 $i$ 位，且深度模 $2^i$ 余 $j$ 的贡献。

为了恰好得到子树内的贡献，我们可以先在遍历子树前累加 $w$ ，遍历后再次累加 $w$ ，最后返回即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010;
int n,a[N],w[21][N],res=0;
vector<int>v[N];
int dfs(int x,int y){
    int ans=a[x];
    for(int i=0;i<=20;i++)w[i][(a[x]+y)&((1<<i)-1)]^=(1<<i);
    for(int i=0;i<=20;i++)ans^=w[i][y&((1<<i)-1)];
    for(int u:v[x]){
        ans^=dfs(u,y+1);
    }
    for(int i=0;i<=20;i++)ans^=w[i][y&((1<<i)-1)];
    res+=ans;
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2,x;i<=n;i++){
        cin>>x;
        v[x].push_back(i);
    }
    dfs(1,0);
    cout<<res;
    return 0;
}

P8292 [省选联考 2022] 卡牌

又一个我没有见过的套路。

题目链接： [省选联考 2022] 卡牌。

题目内容：

小 A 有 $n$ 张卡牌，编号为 $1, 2, \ldots, n$ 。每张卡牌上写着一个正整数，第 $i$ 张卡牌上的正整数为 $s_i$ 。

现在有 $m$ 轮游戏，第 $i$ 轮游戏会给出 $c_i$ 个质数，小 A 需要选择任意多张卡牌，使得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。

这当然难不倒小 A，于是他开始思考一个更难的问题，对于每一轮游戏，他有多少种卡牌的选法。

这给小 A 整不会了，于是他只能来求助你，你只需要告诉他答案模 $998244353$ 的值即可。两种选法 A 和 B 互不相同当且仅当存在一张卡牌在 A 中被选择但在 B 中未被选择或者存在一张卡牌在 B 中被选择但在 A 中未被选择。注意：牌面上的数字相同但编号不相同的两张卡牌被视为不同的卡牌。

对于 $100 \%$ 的数据， $1 \le n \le {10}^6$ ， $1 \le s_i \le 2000$ ， $1 \le m \le 1500$ ， $1 \le c_i, \sum_i c_i \le 18000$ ， $2 \le p_{i, j} \le 2000$ 。

测试点 $n \le$ $m \le$ $\sum_i c_i \le$ 其他限制

$1 \sim 2$ $10$ $10$ $20$ $s_i \le 30$

$3 \sim 5$ $10$ $20$ $50$ 无

$6 \sim 8$ ${10}^6$ $1500$ $10000$ $s_i \le 30$

$9 \sim 11$ $10000$ $1000$ $5000$ $s_i \le 500$

$12 \sim 13$ $1000$ $100$ $1000$ 无

$14 \sim 17$ $5000$ $600$ $7000$ 无

$18 \sim 20$ ${10}^6$ $1500$ $18000$ 无

测试点	$n \le$	$m \le$	$\sum_i c_i \le$	其他限制
$1 \sim 2$	$10$	$10$	$20$	$s_i \le 30$
$3 \sim 5$	$10$	$20$	$50$	无
$6 \sim 8$	${10}^6$	$1500$	$10000$	$s_i \le 30$
$9 \sim 11$	$10000$	$1000$	$5000$	$s_i \le 500$
$12 \sim 13$	$1000$	$100$	$1000$	无
$14 \sim 17$	$5000$	$600$	$7000$	无
$18 \sim 20$	${10}^6$	$1500$	$18000$	无

对于 $25\%$ 的数据，有 $s_i\le 30$ 。此时质数个数不多，可以直接容斥计算，十分简单。

但是对于 $100\%$ 的数据，有 $s_i\le 2\times10^3$ ，质数个数达到 $303$ 个，直接容斥有 $2^{303}$ 的复杂度，不行。

接下来是一个极为 Ynoi 的想法：根号分治。

注意到 $43\times 47>2\times10^3$ ，也就是说，对于任意一个 $s_i$ ，其最多之后有一个大于等于 $43$ 的质因数。

那么，对于所有大于等于 $43$ 的质数，我不需要容斥也能直接统计答案。

那么，接下来要做的事情就是状压前面的小质数，计算在不选某些质数的情况下的答案，最后容斥即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5010,M=18010,P=998244353;
int n,m,a[N],p[N],cnt,book[N],id[N],f[(1<<13)+5][350],tt[(1<<13)+5],q[N],b[N],pw[1000010];
vector<int>v[N];
void get_prime(int x){
    for(int i=2;i<=x;i++){
        if(!book[i])p[++cnt]=i,id[i]=cnt;
        for(int j=1;j<=cnt&&i*p[j]<=x;j++){
            book[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=1;j*p[i]<=x;j++){
            if(i<=13)q[j*p[i]]|=(1<<i-1);
            v[j*p[i]].push_back(i);
        }
    }
}
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
int main(){
    scanf("%d",&n);
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=2ll*pw[i-1]%P;
    get_prime(2000);
    for(int i=1,x;i<=n;i++)scanf("%d",&x),a[x]++;
    //cout<<v[4].size()<<"\n";
    for(int i=0;i<(1<<13);i++){
      //  cout<<i<<"\n";
        for(int j=2;j<=2000;j++){
            if(q[j]&i)continue;
            // if(v[j].size()==0){
            //     cout<<j<<"\n";
            //     throw 1;
            // }
            (f[i][v[j].back()]+=a[j])%=P;
            tt[i]+=a[j];
        }
        tt[i]+=a[1];
    }
    scanf("%d",&m);
    while(m--){
        int c;
        scanf("%d",&c);
        for(int i=1;i<=c;i++)scanf("%d",&b[i]);
        sort(b+1,b+1+c);c=unique(b+1,b+1+c)-b-1;
        int les=0;
        for(int i=1;i<=c;i++)if(id[b[i]]<=13)les|=(1<<id[b[i]]-1);
        int res=0;
        for(int i=0;i<(1<<13);i++){
            if((les|i)!=les)continue;
            int ans=1,ct=tt[i];
            for(int j=1;j<=c;j++){
                if(b[j]<=41||!f[i][id[b[j]]])continue;
                ans=1ll*ans*(pw[f[i][id[b[j]]]]+P-1)%P;
                ct-=f[i][id[b[j]]];
            }
            ans=1ll*ans*pw[ct]%P;
            if(__builtin_popcount(i)&1)(res+=P-ans)%=P;
            else (res+=ans)%=P;
        }
        printf("%d\n",res);
    }
    return 0;
}

P11831 [省选联考 2025] 追忆

我常常追忆过去。追忆我之前到底是怎么写出这一题目的。

题目链接： [省选联考 2025] 追忆。

题目背景 & 描述：

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

给定一个 $n$ 个点 $m$ 条边的有向图 $G$ ，结点由 $1$ 至 $n$ 编号。第 $i$ ( $1 \leq i \leq m$ ) 条边从 $u_i$ 指向 $v_i$ ，保证 $u_i < v_i$ 。节点 $j$ ( $1 \leq j \leq n$ ) 有两个权值 $a_j, b_j$ ，保证 $[a_1, \ldots, a_n]$ 与 $[b_1, \ldots, b_n]$ 均是 $1 \sim n$ 的排列。

你需要进行 $q$ 次操作。操作有以下三种：

$1\ x\ y$ ：交换 $a_x$ 和 $a_y$ ；

$2\ x\ y$ ：交换 $b_x$ 和 $b_y$ ；

$3\ x\ l\ r$ ：你需要输出满足以下两个条件的点 $y$ 中 $b_y$ 的最大值，若不存在满足条件的点则输出 $0$ ：

$l \leq a_y \leq r$ 。

图 $G$ 中存在一条 $x$ 到 $y$ 的有向路径，即存在整数 $k \geq 1$ 与 $k$ 个结点 $p_1, p_2, \ldots, p_k$ ，满足 $p_1 = x$ ， $p_k = y$ ，且对于所有 $1 \leq i < k$ ，图 $G$ 中存在从 $p_i$ 指向 $p_{i+1}$ 的有向边。特别地，图 $G$ 中总是存在一条 $x$ 到 $x$ 的有向路径。

对于所有测试点，

$1 \leq T \leq 3$ ，

$1 \leq n, q \leq 10^5$ ， $1 \leq m \leq 2 \times 10^5$ ，

$\forall 1 \leq i \leq m$ ， $1 \leq u_i < v_i \leq n$ ，

$\forall 1 \leq i \leq n$ ， $1 \leq a_i \leq n$ ，且 $[a_1, \ldots, a_n]$ 是 $1 \sim n$ 的一个排列，

$\forall 1 \leq i \leq n$ ， $1 \leq b_i \leq n$ ，且 $[b_1, \ldots, b_n]$ 是 $1 \sim n$ 的一个排列，

$\forall 1 \leq i \leq q$ ， $o_i \in \{1, 2, 3\}$ ， $1 \leq x_i, y_i \leq n$ ， $1 \leq l_i \leq r_i \leq n$ 。

测试点编号 $n, q \leq$ $m \leq$ 特殊性质

$1 \sim 5$ $2\,000$ $4\,000$ 无

$6$ $8 \times 10^4$ $1.6 \times 10^5$ AB

$7$ $6 \times 10^4$ $1.2 \times 10^5$ B

$8, 9$ $8 \times 10^4$ $1.6 \times 10^5$ ^

$10 \sim 12$ ^ ^ AC

$13, 14$ $6 \times 10^4$ $1.2 \times 10^5$ A

$15, 16$ $8 \times 10^4$ $1.6 \times 10^5$ ^

$17$ $6 \times 10^4$ $1.2 \times 10^5$ D

$18$ $8 \times 10^4$ $1.6 \times 10^5$ ^

$19, 20$ $6 \times 10^4$ $1.2 \times 10^5$ 无

$21, 22$ $8 \times 10^4$ $1.6 \times 10^5$ ^

$23 \sim 25$ $10^5$ $2 \times 10^5$ ^

特殊性质 A： $\forall 1 \leq i \leq q, o_i \neq 1$ 。

特殊性质 B： $\forall 1 \leq i \leq q, o_i \neq 2$ 。

特殊性质 C： $\forall 1 \leq i \leq q, l_i = 1, r_i = n$ 。

特殊性质 D：保证在每个 $3$ 操作的时刻， $\forall 1 \leq i \leq n, a_i = b_i$ 。

时间限制 $9s$ （原题 $6s$ ），空间限制 $2GB$ 。

测试点编号	$n, q \leq$	$m \leq$	特殊性质
$1 \sim 5$	$2\,000$	$4\,000$	无
$6$	$8 \times 10^4$	$1.6 \times 10^5$	AB
$7$	$6 \times 10^4$	$1.2 \times 10^5$	B
$8, 9$	$8 \times 10^4$	$1.6 \times 10^5$	^
$10 \sim 12$	^	^	AC
$13, 14$	$6 \times 10^4$	$1.2 \times 10^5$	A
$15, 16$	$8 \times 10^4$	$1.6 \times 10^5$	^
$17$	$6 \times 10^4$	$1.2 \times 10^5$	D
$18$	$8 \times 10^4$	$1.6 \times 10^5$	^
$19, 20$	$6 \times 10^4$	$1.2 \times 10^5$	无
$21, 22$	$8 \times 10^4$	$1.6 \times 10^5$	^
$23 \sim 25$	$10^5$	$2 \times 10^5$	^

容易看出原图是一个 DAG ，并且每一个点 $i$ 能到达的点固定。

先考虑不看操作 1,2 ，只有操作 3 是怎么做。

这个时候发现限制实在是多：不仅要求 $x$ 能到，还要求 $l\le a_y\le r$ 。

此时再看时间限制 $9s$ ，空间限制 $2GB$ ，不难想到使用 bitset 完成这些操作。

为了不导致歧义，令原来的 $a$ 为 $a$ ， $b$ 为 $c$ 。

那么具体的，先拓扑排序得到每个点能到的集合 $b$ 。

然后对于 $l\le a_y\le r$ ，可以前缀和得到合法的集合。

然后把他们求交后得到了一个满足条件的一个新的 bitset 。

问题此时变成了给定 $c$ 数组，每个数是否有效取决于每次询问给定的一个 bitset ，然后求有效数字的最大值。

这个问题正常的想法是处理出 $c$ 的值域数组，不过由于是排列，值域数组里的每一个数代表这个数对应的下标在哪里出现的。

然后类似于对 $a$ 的处理，对值域数组建立 `bitset’ 并前缀和。

最后只需要二分找最大值出现的位置即可。

问题基本上已经解决了。

接下来就是对于 $a$ 和 $c$ 的修改上的问题了。

这里比较简单，只需要将前缀和数组改为分块即可。

然后就追忆成功了。

追忆：

#include <bits/stdc++.h>
using namespace std;
const int N=100010,B=350;
int n,m,Q,CCC,T,rd[N],q[N],loc[N],a[N],c[N],A[N],C[N];
vector<int>v[N];
bitset<N>b[N],w[B],t[B],tmp;
int main(){
    scanf("%d%d",&CCC,&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&Q);
        for(int i=1;i<=n;i++){
            v[i].clear();rd[i]=0;
            b[i].reset();
            b[i][i]=1;loc[i]=(i-1)/B+1;
        }
        for(int i=1;i<=loc[n];i++)w[i].reset(),t[i].reset();
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            v[y].push_back(x);
            rd[x]++;
        }
        int head=0,tail=0;
        for(int i=1;i<=n;i++)if(rd[i]==0)q[tail++]=i;
        while(head<tail){
            int l=q[head++];
            for(int i=0;i<v[l].size();i++){
                int u=v[l][i];
                rd[u]--;
                b[u]|=b[l];
                if(rd[u]==0)q[tail++]=u;
            }
        }
        for(int i=1;i<=n;i++)cin>>a[i],w[loc[a[i]]][i]=1,A[a[i]]=i;
        for(int i=1;i<=n;i++)cin>>c[i],t[loc[c[i]]][i]=1,C[c[i]]=i;
        for(int i=2;i<=loc[n];i++)w[i]|=w[i-1];
        for(int i=loc[n]-1;i>=1;i--)t[i]|=t[i+1];
        while(Q--){
            int opt,x,y,z;
            scanf("%d%d%d",&opt,&x,&y);
            switch(opt){
                case 1:
                    for(int i=loc[a[x]];i<=loc[n];i++)w[i][x]=0;
                    for(int i=loc[a[y]];i<=loc[n];i++)w[i][y]=0;
                    for(int i=loc[a[x]];i<=loc[n];i++)w[i][y]=1;
                    for(int i=loc[a[y]];i<=loc[n];i++)w[i][x]=1;
                    swap(a[x],a[y]);
                    swap(A[a[x]],A[a[y]]);
                    break;
                case 2:
                    for(int i=loc[c[x]];i>=1;i--)t[i][x]=0;
                    for(int i=loc[c[y]];i>=1;i--)t[i][y]=0;
                    for(int i=loc[c[x]];i>=1;i--)t[i][y]=1;
                    for(int i=loc[c[y]];i>=1;i--)t[i][x]=1;
                    swap(c[x],c[y]);
                    swap(C[c[x]],C[c[y]]);
                    break;
                case 3:
                    scanf("%d",&z);
                    if(loc[y]==loc[z]){
                        tmp.reset();
                        for(int i=y;i<=z;i++){
                            if(b[x][A[i]])tmp[A[i]]=1;
                        }
                    }
                    else{
                        tmp=b[x]&(w[loc[z]-1]^w[loc[y]]);
                        for(int i=y;i<=loc[y]*B;i++){
                            if(b[x][A[i]])tmp[A[i]]=1;
                        }
                        for(int i=(loc[z]-1)*B+1;i<=z;i++){
                            if(b[x][A[i]])tmp[A[i]]=1;
                        }
                    }
                    int l=1,r=loc[n];
                    while(l<r){
                        int mid=(l+r+1)>>1;
                        if((t[mid]&tmp).any())l=mid;
                        else r=mid-1;
                    }
                    int flag=0;
                    for(int i=(l==loc[n]?n:l*B);i>=(l-1)*B+1;i--){
                        if(tmp[C[i]]){
                            printf("%d\n",i);
                            flag=1;
                            break;
                        }
                    }
                    if(!flag)printf("0\n");
                    break;
            }
        }
    }
    return 0;
}