显然无法用 polylog 的数据结构维护，序列分块也不行，考虑询问分块。每 \(B\) 个询问处理一次。
将这个询问中 \(2,3\) 操作涉及到的点设为“关键点”，那么容易发现，环上每一段以关键点结尾的链在这块操作的过程中始终保持不变，也就是说我们可以把它们缩在一起。
先预处理出每个块的增量对每组询问的答案的贡献系数，这可以一遍 two pointers 求出，随后询问就可以通过实时维护一个增量数组求出。\(2\) 操作就直接对环上的每个段令其增量数组 \(+v\) 即可，由于关键点个数是 \(O(B)\) 的所以修改的位置也是 \(O(B)\) 的。\(3\) 操作直接换。取 \(B=\sqrt{q}\) 即可。总复杂度 \(O(q\sqrt{q})\)。
const int MAXN=2e5;
const int BLK=500;
int n,qu,p[MAXN+5];ll a[MAXN+5],s[MAXN+5];
struct qry{int opt,x,y;}q[MAXN+5];
struct dat{
int x,coef,id;
friend bool operator <(const dat &X,const dat &Y){
return X.x<Y.x;
}
}d[BLK*2+5];
bool vis[MAXN+5];
int nxt[MAXN+5],id[MAXN+5],coef[BLK+5][BLK*2+5],len,tmp[BLK*2+5],dcnt;
ll add[BLK*2+5];
void deal(int l,int r){
// printf("deal %d %d\n",l,r);
memset(vis,0,sizeof(vis));memset(nxt,0,sizeof(nxt));
memset(id,0,sizeof(id));memset(coef,0,sizeof(coef));len=dcnt=0;
memset(tmp,0,sizeof(tmp));memset(add,0,sizeof(add));
for(int i=l;i<=r;i++){
if(q[i].opt==1)d[++dcnt]={q[i].x-1,-1,i-l},d[++dcnt]={q[i].y,1,i-l};
else if(q[i].opt==2)vis[q[i].x]=1;
else vis[q[i].x]=vis[q[i].y]=1;
}
for(int i=1;i<=n;i++)if(vis[i]){
int cur=p[i];vector<int>vec;
while(!vis[cur])vec.pb(cur),cur=p[cur];
vec.pb(cur);id[cur]=++len;
for(int x:vec)nxt[x]=cur;
}
// for(int i=1;i<=n;i++)printf("%d%c",nxt[i]," \n"[i==n]);
// for(int i=1;i<=n;i++)printf("%d%c",id[i]," \n"[i==n]);
sort(d+1,d+dcnt+1);
for(int i=1,j=1;i<=dcnt;i++){
while(j<=d[i].x){tmp[id[nxt[j]]]++;++j;}
for(int k=1;k<=len;k++)coef[d[i].id][k]+=d[i].coef*tmp[k];
}
for(int i=l;i<=r;i++){
if(q[i].opt==1){
ll res=s[q[i].y]-s[q[i].x-1];
for(int k=1;k<=len;k++)res+=add[k]*coef[i-l][k];
printf("%lld\n",res);
}else if(q[i].opt==2){
int cur=p[q[i].x];
do{
add[id[nxt[cur]]]+=q[i].y;cur=p[nxt[cur]];
}while(cur!=p[q[i].x]);
}else swap(p[q[i].x],p[q[i].y]);
}
for(int i=1;i<=n;i++)a[i]+=add[id[nxt[i]]],s[i]=s[i-1]+a[i];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
scanf("%d",&qu);int blk_sz=(int)sqrt(qu),cur=0;
for(int i=1;i<=qu;i++)scanf("%d%d%d",&q[i].opt,&q[i].x,&q[i].y);
for(int i=1;i<=qu;i++){
++cur;
if(cur==blk_sz)deal(i-cur+1,i),cur=0;
}
if(cur)deal(qu-cur+1,qu);
return 0;
}