CF1083C Max Mex

鬼题一道去年开始写然后咕了很久很久现在再写。

考的知识点倒是挺经典的算法线段树维护树上直径。

一棵树有点权点权为排列每次询问求出树上一条链的mex的最大值或者交换两个点的点权。

analysis：对于这种没有指定链的问题我们都需要一个数据结构来动态维护答案或者就在每次修改完就更新答案一般采用的都是线段树而这道题也是如此利用线段树来维护mex的最大值。

具体维护：我们只关心0 1 2 3 4...这些数值的点是否能串成链可以想到用线段树来维护数值区间区间有几个信息 L R表示这个区间的数值能否利用L~R这条链给表示出来这样我们进行区间与区间之间的合并即可。

怎么合并：考虑两个区间四个端点可以证明其他的在这四个端点中间的那些点是没有必要的这个可以反证。那么如果可以合成一条链那么这条链的端点肯定也是由这四个点钟的两个点组成的，C(4,2)=6.所以有6种情况，我们暴力枚举哪两个点然后如何判断？可以发现那么剩下的两个点一定都会在L,R的链上我们可以利用LCA来判断剩下的两个点是否在当前组成的链上，如果在那么说明合并成功了。

考虑求出答案线段树里只存放了区间合并的结果并没有答案我们在线段树上二分即可。

实际写起来比较ex.

最后再点一下怎么判断一个点在一条链上：设当前链为x,y lca=LCA(x,y) 判断点w 充要条件：(LCA(x,w)w||LCA(y,w)w)&&LCA(lca,w)==lca.

可以自己画一下图感受一下。

(看了一眼以前代码 pushup 写的非常鬼畜 ST表写挂了 ask写挂了反正一堆毛病...

又写了一遍觉得不是很难写但是觉得处理还是有点麻烦了。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#define INF 100000000000000000ll
#define ll long long
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define db double
#define EPS 1e-5
#define us unsigned
#define l(p) t[p].l
#define r(p) t[p].r
#define zz p<<1
#define yy p<<1|1
using namespace std;
char *fs,*ft,buf[1<<15];
inline char getc()
{
	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=200010;
int n,Q,cnt;
int a[MAXN],L,R,ans;
int Log[MAXN<<1],v[MAXN<<1],d[MAXN],fir[MAXN],pos[MAXN];
int f[MAXN<<1][20],q[2];
vector<int>g[MAXN];
struct wy
{
	int b[2];
	int l,r;
	int sum;
}t[MAXN<<2];
inline int cmp(int x,int y){return d[x]<d[y]?x:y;}
inline void dfs(int x)
{
	fir[x]=++cnt;v[cnt]=x;
	for(us int i=0;i<g[x].size();++i)
	{
		int tn=g[x][i];
		d[tn]=d[x]+1;
		dfs(tn);
		v[++cnt]=x;
	}
}
inline int LCA(int x,int y)
{
	if(!x||!y)return 0;
	x=fir[x];y=fir[y];
	if(x>y)swap(x,y);
	int w=Log[y-x+1];
	return cmp(f[x][w],f[y-(1<<w)+1][w]);
}
inline void pushup(int p)//C(4,2) = 6
{
	for(int i=0;i<=1;++i)
	{
		for(int j=0;j<=1;++j)
		{
			int lca=LCA(t[zz].b[i],t[yy].b[j]);
			if(!lca)continue;
			if((LCA(t[zz].b[i],t[zz].b[i^1])==t[zz].b[i^1]||LCA(t[zz].b[i^1],t[yy].b[j])==t[zz].b[i^1]))
			{
				if(LCA(lca,t[zz].b[i^1])==lca&&LCA(lca,t[yy].b[j^1])==lca)
				{
					if((LCA(t[zz].b[i],t[yy].b[j^1])==t[yy].b[j^1]||LCA(t[yy].b[j^1],t[yy].b[j])==t[yy].b[j^1]))
					{
						t[p].b[0]=t[zz].b[i];t[p].b[1]=t[yy].b[j];
						return;
					}
				}
			}
		}
	}
	int lca=LCA(t[zz].b[0],t[zz].b[1]);
	if(lca)
	{
		if((LCA(t[zz].b[0],t[yy].b[0])==t[yy].b[0]||LCA(t[zz].b[1],t[yy].b[0])==t[yy].b[0]))
			if(LCA(lca,t[yy].b[0])==lca&&LCA(lca,t[yy].b[1])==lca)
				if((LCA(t[zz].b[0],t[yy].b[1])==t[yy].b[1]||LCA(t[zz].b[1],t[yy].b[1])==t[yy].b[1]))
				{
					t[p].b[0]=t[zz].b[0];t[p].b[1]=t[zz].b[1];
					return;
				}
	}
	lca=LCA(t[yy].b[0],t[yy].b[1]);
	if(lca)
	{
		if((LCA(t[yy].b[0],t[zz].b[0])==t[zz].b[0]||LCA(t[yy].b[1],t[zz].b[0])==t[zz].b[0]))
			if(LCA(lca,t[zz].b[0])==lca&&LCA(lca,t[zz].b[1])==lca)
				if((LCA(t[yy].b[0],t[zz].b[1])==t[zz].b[1]||LCA(t[yy].b[1],t[zz].b[1])==t[zz].b[1]))
				{
					t[p].b[0]=t[yy].b[0];t[p].b[1]=t[yy].b[1];
					return;
				}
	}
	t[p].b[0]=t[p].b[1]=0;
}
inline void build(int p,int l,int r)
{
	l(p)=l;r(p)=r;
	if(l==r)
	{
		t[p].b[0]=t[p].b[1]=pos[l];
		return;
	}
	int mid=(l+r)>>1;
	build(zz,l,mid);
	build(yy,mid+1,r);
	pushup(p);
}
inline void change(int p,int x)
{
	if(l(p)==r(p))
	{
		t[p].b[0]=t[p].b[1]=pos[l(p)];
		return;
	}
	int mid=(l(p)+r(p))>>1;
	if(x<=mid)change(zz,x);
	else change(yy,x);
	pushup(p);
}
inline int merge(int *a,int *b)
{
	if(!a[0]){a[0]=b[0];a[1]=b[1];return 1;}
	for(int i=0;i<=1;++i)
	{
		for(int j=0;j<=1;++j)
		{
			int lca=LCA(a[i],b[j]);
			if(!lca)continue;
			if((LCA(a[i],a[i^1])==a[i^1]||LCA(a[i^1],b[j])==a[i^1]))
				if(LCA(lca,a[i^1])==lca&&LCA(lca,b[j^1])==lca)
					if((LCA(a[i],b[j^1])==b[j^1]||LCA(b[j^1],b[j])==b[j^1]))
					{
						a[0]=a[i];a[1]=b[j];
						return 1;
					}
		}
	}
	int lca=LCA(a[0],a[1]);
	if(lca)
	{
		if((LCA(a[0],b[0])==b[0]||LCA(a[1],b[0])==b[0]))
				if(LCA(lca,b[0])==lca&&LCA(lca,b[1])==lca)
					if((LCA(a[0],b[1])==b[1]||LCA(a[1],b[1])==b[1]))return 1;
	}
	lca=LCA(b[0],b[1]);
	if(lca)
	{
		if((LCA(b[0],a[0])==a[0]||LCA(b[1],a[0])==a[0]))
			if(LCA(lca,a[0])==lca&&LCA(lca,a[1])==lca)
				if((LCA(b[0],a[1])==a[1]||LCA(b[1],a[1])==a[1])){a[0]=b[0];a[1]=b[1];return 1;}
	}
	return 0;
}
inline int ask(int p)
{
	if(t[p].b[1]&&t[p].b[0])
	{
		if(merge(q,t[p].b)){ans=max(ans,r(p));return 1;}
		if(l(p)!=r(p))if(ask(zz))ask(yy);
		return 0;
	}
	if(ask(zz))ask(yy);
	return 0;
}
int main()
{
	freopen("1.in","r",stdin);
	n=read();
	for(int i=1;i<=n;++i)a[i]=read()+1,pos[a[i]]=i;
	for(int i=2;i<=n;++i)g[read()].push_back(i);
	dfs(1);Log[0]=-1;
	for(int i=1;i<=cnt;++i)
	{
		Log[i]=Log[i>>1]+1;
		f[i][0]=v[i];
	}
	for(int j=1;j<=Log[cnt];++j)
		for(int i=1;i<=cnt-(1<<j)+1;++i)
			f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	build(1,1,n);
	Q=read();
	for(int i=1;i<=Q;++i)
	{
		int op;
		int x,y;
		op=read();
		if(op==1)
		{
			x=read();y=read();
			swap(a[x],a[y]);
			pos[a[x]]=x;
			pos[a[y]]=y;
			change(1,a[x]);
			change(1,a[y]);
		}
		else 
		{
			q[0]=q[1]=ans=0;ask(1);
			printf("%d
",ans);
		}
	}
	return 0;
}