TLE on test 16/ll

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,B=450;
int n,q,idx,a[N],p[N],o[N],op[N],x[N],y[N],sum[N],tag[N],rt[N],rd[N],id[N],vis[N],cnt[N],pre[1003][1003];
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void getrt(int v,int u){for(;!rt[v];v=o[v])rt[v]=u;}
void update(int u,int w)
{
	for(;!vis[u];u=rt[p[u]]){vis[u]=1;tag[u]+=w;}
	for(;vis[u];u=rt[p[u]])vis[u]=0;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++){p[i]=read();o[p[i]]=i;}
	q=read();
	for(int i=1;i<=q;i++){op[i]=read();x[i]=read();y[i]=read();}
	for(int l=1,r=B;l<=q;l+=B,r+=B)
	{
		r=min(r,q);
		for(int i=0;i<=n;i++)
		{
			cnt[i]=rt[i]=tag[i]=id[i]=0;
			if(i)sum[i]=sum[i-1]+a[i]; 
		}
		idx=0;
		for(int i=l;i<=r;i++)
		{
			if(op[i]>1)rt[x[i]]=x[i];
			else
			{
				if(!id[x[i]-1])id[x[i]-1]=++idx;
				if(!id[y[i]])id[y[i]]=++idx;
			}
			if(op[i]>2)rt[y[i]]=y[i]; 
		}
		idx=0;
		for(int i=1;i<=n;i++)if(rt[i]==i)
		{
			rt[i]=0;rd[++idx]=i;
			getrt(i,i);
		}
		for(int i=0;i<=n;i++)
		{
			cnt[rt[i]]++;
			for(int j=1;j<=idx;j++)pre[id[i]][j]=cnt[rd[j]];
		}
		for(int i=l,ans;i<=r;i++)
		{
			if(op[i]==1)
			{
				ans=sum[y[i]]-sum[x[i]-1];
				for(int j=1;j<=idx;j++)ans+=tag[rd[j]]*(pre[id[y[i]]][j]-pre[id[x[i]-1]][j]);
				printf("%lld\n",ans);
			}
			if(op[i]==2)update(x[i],y[i]);
			if(op[i]==3)
			{
				swap(p[x[i]],p[y[i]]);
				swap(o[p[x[i]]],o[p[y[i]]]);
			}
		}
		for(int i=1;i<=n;i++)a[i]+=tag[rt[i]];
	}
}