P5397 卡不过去pwp。

代码：

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
	il int read(){
		int x=0,f=1;char ch=gc;
		while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
		return x*f;
	}
	il int qmi(int a,int b,int p){
		int ans=1;
		while(b){
			if(b&1) ans=ans*a%p;
			a=a*a%p,b>>=1;
		}
		return ans;
	}
	// il auto max(auto a,auto b){return (a>b?a:b);}
	// il auto min(auto a,auto b){return (a<b?a:b);}
	il int gcd(int a,int b){
		if(!b) return a;
		return gcd(b,a%b);
	}
	il int lcm(int a,int b){
		return a/gcd(a,b)*b;
	}
	il void exgcd(int a,int b,int &x,int &y){
		if(!b) return x=1,y=0,void(0);
		exgcd(b,a%b,x,y);
		int t=x;
		x=y,y=t-a/b*x;
		return ;
	}
	// mt19937 rnd(time(0));
}
using namespace yzqwq;
#define inf 1e5+2

const int N=1e5+1,K=451,M=N/K+3;
int n,m,a[N];
short id[M][N];
int lstans;
short len,G;
int dis[M][K][K];
//第i个块(序列)中值j与k的最小距离
int fi[M][K],ls[M][K];

il void modify(int x,int y){
    //x->y
    if(x==y) return ;
    for(re short bk=1;bk<=G;++bk)
    if(id[bk][x])
        if(id[bk][y]){
            for(re short i=1;i<=id[bk][y];++i){
                if(i<=id[bk][x]) 
                    dis[bk][i][id[bk][y]]=(dis[bk][i][id[bk][y]]>dis[bk][i][id[bk][x]]?dis[bk][i][id[bk][x]]:dis[bk][i][id[bk][y]]),
                    dis[bk][i][id[bk][x]]=inf;
                else
                    dis[bk][i][id[bk][y]]=(dis[bk][i][id[bk][y]]>dis[bk][id[bk][x]][i]?dis[bk][id[bk][x]][i]:dis[bk][i][id[bk][y]]);
            }
            for(re short i=id[bk][y];i<=len;++i){
                if(i<=id[bk][x])
                    dis[bk][id[bk][y]][i]=(dis[bk][id[bk][y]][i]>dis[bk][i][id[bk][x]]?dis[bk][i][id[bk][x]]:dis[bk][id[bk][y]][i]),
                    dis[bk][i][id[bk][x]]=inf;
                else 
                    dis[bk][id[bk][y]][i]=(dis[bk][id[bk][y]][i]>dis[bk][id[bk][x]][i]?dis[bk][id[bk][x]][i]:dis[bk][id[bk][y]][i]);
            }               
            
            fi[bk][id[bk][y]]=(fi[bk][id[bk][y]]>fi[bk][id[bk][x]]?fi[bk][id[bk][x]]:fi[bk][id[bk][y]]);
            ls[bk][id[bk][y]]=(ls[bk][id[bk][y]]<ls[bk][id[bk][x]]?ls[bk][id[bk][x]]:ls[bk][id[bk][y]]);
            id[bk][x]=0;
        }
        else{
            id[bk][y]=id[bk][x];
            id[bk][x]=0; 
        }
    return ;
}
il int query(int x,int y){
    int Min=inf,r1=0,r2=0;
    for(re short i=1;i<=G;++i){
        short X=id[i][x],Y=id[i][y];
        if(X>Y) swap(X,Y);
        if(id[i][x]&&id[i][y]) Min=(Min>dis[i][X][Y]?dis[i][X][Y]:Min);
        if(id[i][x]&&r2) Min=(Min>fi[i][id[i][x]]-r2?fi[i][id[i][x]]-r2:Min);
        if(id[i][y]&&r1) Min=(Min>fi[i][id[i][y]]-r1?fi[i][id[i][y]]-r1:Min);
        if(id[i][x]) r1=ls[i][id[i][x]];
        if(id[i][y]) r2=ls[i][id[i][y]];
        if(Min<=1) return Min;
    }
    return Min;
}

il void solve(){
    memset(dis,0x3f,sizeof(dis));
    n=rd,m=rd,len=K-1,G=(n-1)/len+1;
    for(re int i=1;i<=n;++i) a[i]=rd;

    for(re short i=1;i<=G;++i){
        short idx=0;
        for(re int j=(i-1)*len+1;j<=min(n,i*len);++j){
            if(!id[i][a[j]]) id[i][a[j]]=++idx,fi[i][id[i][a[j]]]=j;
            ls[i][id[i][a[j]]]=j;
        }
        for(re int j=(i-1)*len+1;j<=min(n,i*len);++j)
        for(re int k=(i-1)*len+1;k<=min(n,i*len);++k)
            dis[i][id[i][a[j]]][id[i][a[k]]]=(dis[i][id[i][a[j]]][id[i][a[k]]]>(k-j<0?j-k:k-j)?(k-j<0?j-k:k-j):dis[i][id[i][a[j]]][id[i][a[k]]]);
    }

    while(m--){
        short op=rd;
        int x=rd,y=rd;
        x^=lstans,y^=lstans;
        if(op==1) modify(x,y);
        else{
            int ans=query(x,y);
            if(ans>=inf) printf("Ikaros\n"),lstans=0;
            else printf("%d\n",lstans=ans);
        }
    }
	return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int t=1;while(t--)
	solve();
	return 0;
}