码力人的甜品，口嗨者的末路。
感觉手牵手那个题才是第四分块正体，这个不如叫最初根号分治。
思路
根号分治。
对于每个值，把它们分成出现大于根号次和小于等于根号次两类。
先考虑不带修的问题。
对于大于根号次的值显然至多只有根号个，可以暴力 \(O(n)\) 预处理出和它有关的答案。
对于小于等于根号次的值，显然可以暴力归并或者 vector 二分求答案，归并单次的复杂度是根号。
带修的话，分讨一下贡献。
- 两个根号次以内的值，合并后还是根号次以内
直接归并。
- 两个大于根号次的值
因为至多只会有根号次这样的合并，所以可以暴力。
- 一个根号次以内的值和一个大于根号次的值
这个比较麻烦，要拆一下贡献。
可以把这个小于根号次的值暂时先归并到另一个值内，然后询问时和预处理出的答案一起算贡献。
大于根号次时只能暴力重构，但是因为至多有根号次，所以复杂度也是对的。
注意可能会有合并未出现的值一类的边界情况，所以还要套路地维护每个值真实情况下代表的值。
时间复杂度 \(O(n \sqrt{n})\)
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
const int sq = 320;
const int inf = 0x3f3f3f;
int n, m, cur, lim;
int a[maxn], sz[maxn], id[maxn], fa[maxn];
int ans[sq][maxn];
vector<int> pos[maxn];
namespace IO
{
//by cyffff
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 26) + 1];
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define reg register
inline int read()
{
reg char ch = gh();
reg int x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void putc(char ch) { out[len++] = ch; }
template<class T>
inline void write(T x)
{
if (x < 0) putc('-'), x = -x;
if (x > 9) write(x / 10);
out[len++] = x % 10 + 48;
}
inline void flush()
{
fwrite(out, 1, len, stdout);
len = 0;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;
inline void build(int x, int _id = 0)
{
id[x] = _id ? _id : ++cur;
int t = id[x];
memset(ans[t], 0x3f, (n + 1) * sizeof(int));
for (int i = 1, j = inf; i <= n; i++)
if (a[i] == x) j = 0;
else ans[t][a[i]] = min(ans[t][a[i]], ++j);
for (int i = n, j = inf; i >= 1; i--)
if (a[i] == x) j = 0;
else ans[t][a[i]] = min(ans[t][a[i]], ++j);
vector<int> emp;
ans[t][x] = 0, pos[x].swap(emp);
}
inline void merge(int x, int y)
{
int lx = pos[x].size(), ly = pos[y].size(), i, j;
vector<int> res;
for (i = 0, j = 0; (i < lx) && (j < ly); ) res.push_back(pos[x][i] < pos[y][j] ? pos[x][i++] : pos[y][j++]);
while (i < lx) res.push_back(pos[x][i++]);
while (j < ly) res.push_back(pos[y][j++]);
pos[y] = res;
}
inline int qry(int x, int y)
{
int lx = pos[x].size(), ly = pos[y].size(), ans = inf, i, j;
if ((lx == 0) || (ly == 0)) return inf;
for (i = 0, j = 0; (i < lx) && (j < ly); ) ans = min(ans, (pos[x][i] < pos[y][j] ? pos[y][j] - pos[x][i++] : pos[x][i] - pos[y][j++]));
while (i < lx) ans = min(ans, pos[x][i++] - pos[y][ly - 1]);
while (j < ly) ans = min(ans, pos[y][j++] - pos[x][lx - 1]);
return ans;
}
inline void modify(int x, int y)
{
int fx = fa[x], fy = fa[y];
if ((!sz[fx]) || (fx == fy)) return;
if (sz[fx] > sz[fy]) fa[y] = fx, fa[x] = n + 1, swap(fx, fy);
else fa[x] = n + 1;
if ((fx > n) || (fy > n)) return;
x = fx, y = fy;
if (sz[y] <= lim)
{
if (sz[x] + sz[y] <= lim)
{
for (int p : pos[x]) a[p] = y;
for (int i = 1; i <= cur; i++) ans[i][y] = min(ans[i][y], ans[i][x]);
merge(x, y);
}
else
{
for (int i = 1; i <= n; i++)
if (a[i] == x) a[i] = y;
build(y);
}
}
else if (sz[x] <= lim)
{
if (sz[x] + pos[y].size() <= lim)
{
for (int p : pos[x]) a[p] = y;
for (int i = 1; i <= cur; i++) ans[i][y] = min(ans[i][y], ans[i][x]);
merge(x, y);
}
else
{
for (int i = 1; i <= n; i++)
if (a[i] == x) a[i] = y;
build(y, id[y]);
}
}
else
{
for (int i = 1; i <= n; i++)
if (a[i] == x) a[i] = y;
build(y, id[y]);
}
sz[y] += sz[x], sz[x] = 0;
vector<int> emp;
pos[x].swap(emp);
}
inline int query(int x, int y)
{
x = fa[x], y = fa[y];
if ((!sz[x]) || (!sz[y])) return -1;
if (x == y) return 0;
if (sz[x] > sz[y]) swap(x, y);
if (sz[y] <= lim) return qry(x, y);
else if (sz[x] <= lim) return min(ans[id[y]][x], qry(x, y));
return min(qry(x, y), min(ans[id[x]][y], ans[id[y]][x]));
}
int main()
{
n = read(), m = read(), lim = sqrt(n);
for (int i = 1; i <= n; i++) sz[a[i] = read()]++, pos[a[i]].push_back(i), fa[i] = i;
for (int i = 0; i <= n; i++)
if (sz[i] > lim) build(i);
int last_ans = 0;
while (m--)
{
int opt, x, y;
opt = read(), x = read() ^ last_ans, y = read() ^ last_ans;
if (opt == 1) modify(x, y);
else
{
last_ans = query(x, y);
if (~last_ans) write(last_ans), putc('\n');
else last_ans = 0, putc('I'), putc('k'), putc('a'), putc('r'), putc('o'), putc('s'), putc('\n');
}
}
flush();
return 0;
}