#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 100005#define T 350int n,m,opt,l,r,k,block,t,ans;int a[N],b[N],pre[N],nxt[N],num[N];struct data{ int sz,pre,nxt,l,r; int cnt[N];}bl[T];void build(){ for (int i=1;i<=n;++i) { pre[i]=i-1,nxt[i]=i+1; num[i]=(i-1)/block+1; ++bl[num[i]].cnt[a[i]]; } bl[1].l=1,bl[1].r=block,bl[1].nxt=2,bl[1].sz=block; for (int i=2;i<=t;++i) { bl[i].l=bl[i-1].l+block,bl[i].r=bl[i-1].r+block; bl[i].pre=i-1,bl[i].nxt=i+1,bl[i].sz=block; }bl[t].r=n,bl[t].sz=n-bl[t].l+1;}int find(int x){ int now=1,size=0; while (size+bl[now].sz<x) size+=bl[now].sz,now=bl[now].nxt; int pt=bl[now].l; for (int i=size+1;i<x;++i) pt=nxt[pt]; return pt;}void change(int l,int r){ l=find(l),r=find(r); int numl=num[l],numr=num[r],val=a[r]; if (numl==numr) { if (bl[numl].l==l) bl[numl].l=r; if (bl[numr].r==r) bl[numr].r=pre[bl[numr].r]; nxt[pre[r]]=nxt[r]; pre[nxt[r]]=pre[r]; pre[r]=pre[l];nxt[r]=l; nxt[pre[l]]=pre[l]=r; } else { if (bl[numl].l==l) bl[numl].l=r; if (bl[numr].r==r) bl[numr].r=pre[r]; if (bl[numr].l==r) bl[numr].l=nxt[r]; nxt[pre[r]]=nxt[r]; pre[nxt[r]]=pre[r]; pre[r]=pre[l];nxt[r]=l; nxt[pre[l]]=pre[l]=r; --bl[numr].sz;++bl[numl].sz; if (!bl[numr].sz) { bl[bl[numr].pre].nxt=bl[numr].nxt; bl[bl[numr].nxt].pre=bl[numr].pre; } --bl[numr].cnt[val];++bl[numl].cnt[val]; num[r]=numl; }}void query(int l,int r,int k){ l=find(l),r=find(r); int numl=num[l],numr=num[r]; if (numl==numr) { for (int i=l;;i=nxt[i]) { if (a[i]==k) ++ans; if (i==r) break; } return; } if (l==bl[numl].l) l=numl; else { for (int i=l;;i=nxt[i]) { if (a[i]==k) ++ans; if (i==bl[numl].r) break; } l=bl[numl].nxt; } if (r==bl[numr].r) r=numr; else { for (int i=r;;i=pre[i]) { if (a[i]==k) ++ans; if (i==bl[numr].l) break; } r=bl[numr].pre; } for (int i=l;i<=r;i=bl[i].nxt) ans+=bl[i].cnt[k];}void rebuild(){ int now=0; for (int i=bl[1].l;now<=n;i=nxt[i]) b[++now]=a[i]; for (int i=1;i<=n;++i) a[i]=b[i]; memset(bl,0,sizeof(bl)); build();}int main(){ freopen("array.in","r",stdin); freopen("array.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); block=sqrt(n);t=(n-1)/block+1; build(); scanf("%d",&m); for (int i=1;i<=m;++i) { scanf("%d",&opt); if (opt==1) { scanf("%d%d",&l,&r); if (l>r) swap(l,r); if (l==r) continue; change(l,r); } else { scanf("%d%d%d",&l,&r,&k); if (l>r) swap(l,r); ans=0;query(l,r,k); printf("%d/n",ans); } if (i%20000==0) rebuild(); }}
