Max Mex

和线段树维护直径集合一样的 trick。

思路

如果一条路径 \(a\) 包含 \([l,r]\) 权值中的所有点，另一条路径 \(b\) 包含和 \([x,y]\) 权值中的所有点构成的。

那么对于一条路径包含 \([l,r]\cup [x,y]\) 权值中的点，其端点一定在 \(a\) 和 \(b\) 的端点间出现。

其条件就是，有以 \(a,b\) 为端点的路径包含 \(a,b\) 的剩下的端点，可以通过 \(dfn\) 相邻的点的路径长度，和最长的端点间的路径长度来判断是否形成一条路径，具体实现看代码。

考虑用线段树维护区间内权值的点组成路径的端点，合并区间即可。

对于查询，在线段树上二分，如果左子树与之前求出的区间可以合并成一条链，向右子树搜索并合并区间；否则向左子树搜索，最后停下来的节点就是答案。

CODE

/*
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define se second

inline int read()
{
	char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int maxn=2e5+5;

int n,cok;
int dep[maxn],st[maxn][25],dfn[maxn],p[maxn],fp[maxn];

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn];
    inline void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}T;

inline void dfs(int u,int f)
{
    dep[u]=dep[f]+1,dfn[u]=++cok;
    st[dfn[u]][0]=f;
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        dfs(v,u);
    }
}
inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
inline void init()
{
    for(int len=1;len<=log2(n);len++)
        for(int i=1;i<=n-(1<<len)+1;i++) st[i][len]=Min(st[i][len-1],st[i+(1<<(len-1))][len-1]);
}
inline int Lca(int x,int y)
{
    if(!(x^y)) return x;
    if(dfn[x]>dfn[y]) swap(x,y);
    int l=dfn[x]+1,r=dfn[y],k=log2(r-l+1);
    return Min(st[l][k],st[r-(1<<k)+1][k]);
}
inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[Lca(x,y)];}

namespace linetree
{
#define lch(p) p<<1
#define rch(p) p<<1|1
    pii tr[maxn*8];
    inline bool cmp(int a,int b){return dfn[a]<dfn[b];}
    inline pii merge(pii a,pii b)
    {
        if(a.fi==0||b.fi==0||a.fi==-1||b.fi==-1) return {0,0};
        vector<int>vec;
        vec.push_back(a.fi),vec.push_back(a.se);
        vec.push_back(b.fi),vec.push_back(b.se);
        sort(vec.begin(),vec.end(),cmp);
        int sum=(dis(vec[0],vec[1])+dis(vec[1],vec[2])+dis(vec[2],vec[3])+dis(vec[3],vec[0]))/2;
        for(int i=0;i<4;i++)
        {
            for(int j=i+1;j<4;j++)
            {
                if(dis(vec[i],vec[j])==sum) return {vec[i],vec[j]};
            }
        }
        return {0,0};
    }
    inline void updata(int p){tr[p]=merge(tr[lch(p)],tr[rch(p)]);}
    inline void build(int p,int l,int r)
    {
        if(l==r) {tr[p]={fp[l],fp[l]};return ;}
        int mid=(l+r)>>1;
        build(lch(p),l,mid),build(rch(p),mid+1,r);
        updata(p);
    }
    inline void insert(int p,int l,int r,int pos,int val)
    {
        if(l==r)
        {
            tr[p]={val,val};
            return ;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) insert(lch(p),l,mid,pos,val);
        else insert(rch(p),mid+1,r,pos,val);
        updata(p);
    }
    inline int qry(int p,int l,int r,pii tmp)
    {
        int mid=(l+r)>>1;
        if(l==r) return l+(merge(tmp,tr[p]).fi>0);
        pii res=merge(tr[lch(p)],tmp);
        if(tmp.fi==-1) res=tr[lch(p)];
        if(res.fi) return qry(rch(p),mid+1,r,res);
        return qry(lch(p),l,mid,tmp);
    }
#undef lch
#undef rch
}
using namespace linetree;

int main()
{
    n=read();
    for(int i=1;i<=n;i++) p[i]=read(),fp[p[i]]=i;
    for(int i=2,x;i<=n;i++) x=read(),T.add(x,i);
    dfs(1,0);
    init();
    linetree::build(1,0,n-1);
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int op,x,y;
        // scanf("%d",&op);
        op=read();
        if(op==1)
        {
            // scanf("%d%d",&x,&y);
            x=read(),y=read();
            swap(fp[p[x]],fp[p[y]]);
            swap(p[x],p[y]);
            linetree::insert(1,0,n-1,p[x],x);
            linetree::insert(1,0,n-1,p[y],y);
        }
        else
        {
            write(linetree::qry(1,0,n-1,{-1,-1}));putchar('\n');
        }
    }
}