这题正解空间应该 $O(n\sqrt n)$ 吧，但是我写了个空间 $O(n)$ 的暴力居然MLE了？？？

我写暴力原本是为了检查我的归并有没有写错，结果 $O(n)$ 的空间直接MLE？我都不敢写正解了。。。

提交记录：https://www.luogu.com.cn/record/37388868

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef double db;
typedef unsigned long long ull;
#define mkp(x,y) make_pair(x,y)
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int N=100009;
const int M=321;
const int inf=0x3f3f3f3f;
int n,m,a[N],lastans;
vector<int>v[N];
void merge(int x,int y) {
	int i=0,j=0,sx=v[x].size(),sy=v[y].size();
	vector<int>res;
	while(i<sx&&j<sy)res.push_back(v[x][i]<v[y][j]?v[x][i++]:v[y][j++]);
	while(i<sx)res.push_back(v[x][i++]);
	while(j<sy)res.push_back(v[y][j++]);
	v[y]=res;
}
int merge_(int x,int y) {
	int i=0,j=0,sx=v[x].size(),sy=v[y].size(),res=inf;
	if(!sx||!sy)return inf;
	while(i<sx&&j<sy)res=min(v[x][i]<v[y][j]?v[y][j]-v[x][i++]:v[x][i]-v[y][j++],res);
	if(i<sx)res=min(res,abs(v[x][i]-v[y][sy-1]));
	if(j<sy)res=min(res,abs(v[x][sx-1]-v[y][j]));
	return res;
}
int query(int x,int y) {
	if(!v[x].size()||!v[y].size())return -1;
	if(x==y)return 0;
	return merge_(x,y);
}
void change(int x,int y) {
	if(x==y)return;
	merge(x,y),v[x].clear();
}
signed main() {
	n=rd(),m=rd();
	for(int i=1;i<=n;++i)v[rd()].push_back(i);
	while(m--) {
		int opt=rd(),x=rd()^lastans,y=rd()^lastans;
		if(opt==1)change(x,y);
		else {
			lastans=query(x,y);
			if(~lastans)printf("%d\n",lastans);
			else lastans=0,puts("Ikaros");
		}
	}
	return 0;
}