春节前做大分块是什么奇妙传统吗……
这个题好想是好想，但是写起来就是另外一回事了……
思路
分块。
第四分块加强版。
区间查询，根号分治做法寄了。
看到合并颜色可以想到一些大分块的套路。类比最初分块，合并颜色可以考虑类似并查集的做法，记录下每个颜色实际上指向的颜色。
接下来考虑不带修时的做法。
分类讨论答案的贡献情况：
-
整块 -> 整块
-
同一整块内的贡献
-
不同整块之间的贡献
-
-
整块（散块）-> 散块（整块）
-
散块 -> 散块
对于 1，同一整块内的贡献可以考虑直接在修改的时候维护。
对于不同整块之间的贡献，令 \(l(b, x)\) 表示第 \(b\) 个整块内 \(x\) 第一次出现的位置，\(r(b, x)\) 表示最后一次出现的位置。显然不同整块之间的贡献是 \(\min l(b + 1, x) - r(b, x)\).
所以考虑对于每个颜色维护 \(l, r\) 即可。
整块和散块之间的贡献类似上面。左侧散块和最左侧整块产生贡献，右侧散块和最右侧整块产生贡献，分讨一下 \(x, y\) 的先后顺序即可。
散块对散块的贡献可以直接动态维护 \(x, y\) 最后一次出现的位置，暴力 \(O(\sqrt{n})\) 查询。
对于每一对颜色直接维护块内的贡献是 \(O(n^2 \sqrt{n})\) 的，所以要考虑对于每个整块内的值进行离散化，总复杂度优化到 \(O(n \sqrt{n})\)
所以一共需要维护的信息是：
-
块内离散化的两个映射
-
\(l, r\)
-
块内答案
接下来考虑修改。
分讨一下情况：
-
块内无 \(x\)，摆烂
-
块内有 \(x\) 无 \(y\)，直接改并查集
-
块内有 \(x\) 有 \(y\)，需要合并贡献
对于 3，先考虑对整块的影响。
\(l, r\) 直接相应取 \(\min\) 和 \(\max\)，离散化的映射相应改一下。问题是如何维护块内答案。
显然只需要将 \(y\) 的答案和 \(x\) 的答案取 \(\min\) 就行 /xk
对于散块直接暴力重构关于 \(x\) 和 \(y\) 的答案。
这样一遍的复杂度是 \(O(\sqrt n)\) 的。
关于时间复杂度：
整块 \(O(n \sqrt{n})\)
标号至多 \(n + 2m\) 个，每次 \(O(\sqrt{n})\)，一共 \(O((n + 2m) \sqrt{n})\)
\(n, m\) 同阶，可以认为是 \(O(n \sqrt{n})\) 的。
代码
#include <cstdio>
#include <cmath>
using namespace std;
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;
const int maxn = 1e5 + 5;
const int sq = 320;
const int inf = 1e9;
inline int min(const int &a, const int &b) { return (a <= b ? a : b); }
inline int max(const int &a, const int &b) { return (a >= b ? a : b); }
#define dis(i, j, k) dis[i][min(j, k)][max(j, k)]
#define chk_min(a, b) a = min(a, b)
#define chk_max(a, b) a = max(a, b)
int n, m;
int block, tot, t;
int st[sq], ed[sq], cur[sq], top[sq];
int a[maxn], b[maxn], bel[maxn], pos[maxn];
int id[sq][maxn];
int val[sq][sq], lft[sq][sq], rgt[sq][sq], stk[sq][sq];
int dis[sq][sq][sq];
inline void init()
{
block = sqrt(n), tot = (n - 1) / block + 1;
for (int i = 1; i <= tot; i++)
{
st[i] = ed[i - 1] + 1, ed[i] = (i == tot ? n : i * block);
int len = ed[i] - st[i] + 1;
for (int j = st[i]; j <= ed[i]; j++)
{
if (!id[i][a[j]]) val[i][id[i][a[j]] = ++cur[i]] = a[j];
b[j] = id[i][a[j]], bel[j] = i;
}
for (int j = len; j >= cur[i] + 1; j--) stk[i][++top[i]] = j;
for (int j = ed[i]; j >= st[i]; j--) lft[i][b[j]] = j;
for (int j = st[i]; j <= ed[i]; j++) rgt[i][b[j]] = j;
for (int j = 1; j <= len; j++)
for (int k = 1; k <= len; k++)
dis[i][j][k] = inf;
for (int j = st[i]; j <= ed[i]; j++)
for (int k = j + 1; k <= ed[i]; k++)
chk_min(dis(i, b[j], b[k]), k - j);
}
}
inline void build(int l, int r, int x, int y)
{
int bl = bel[l], idx = id[bl][x], idy = id[bl][y];
chk_min(lft[bl][idy], lft[bl][idx]), chk_max(rgt[bl][idy], rgt[bl][idx]);
lft[bl][idx] = rgt[bl][idx] = 0, stk[bl][++top[bl]] = idx, id[bl][x] = 0;
for (int i = l; i <= r; i++)
if ((a[i] = val[bl][b[i]]) == x) a[i] = y, b[i] = idy;
for (int i = 1; i <= block; i++) chk_min(dis(bl, i, idy), dis(bl, i, idx)), dis(bl, i, idx) = inf;
}
inline void clear(int bl, int p) { for (int i = st[bl]; i <= ed[bl]; i++) dis(bl, b[i], p) = inf; }
inline void upd_col(int bl, int v)
{
for (int i = st[bl]; i <= pos[1]; i++) chk_min(dis(bl, b[i], v), pos[1] - i);
for (int i = 1; i <= t - 1; i++)
for (int j = pos[i]; j <= pos[i + 1]; j++)
chk_min(dis(bl, b[j], v), min(j - pos[i], pos[i + 1] - j));
for (int i = pos[t]; i <= ed[bl]; i++) chk_min(dis(bl, b[i], v), i - pos[t]);
}
inline void chg_col(int l, int r, int x, int y, int opt)
{
int bl = bel[l], idx = id[bl][x], idy = id[bl][y];
if (!opt) val[bl][id[bl][y] = idy = stk[bl][top[bl]--]] = y;
if (opt == 2) val[bl][idx] = lft[bl][idx] = rgt[bl][idx] = id[bl][x] = 0, stk[bl][++top[bl]] = idx;
t = 0;
for (int i = l; i <= r; i++)
if (a[i] == x) a[i] = y, b[i] = idy, pos[++t] = i;
if (!opt) clear(bl, idy);
upd_col(bl, idy);
if (opt != 2)
{
t = 0;
for (int i = st[bl]; i <= ed[bl]; i++)
if (a[i] == x) pos[++t] = i;
clear(bl, idx), upd_col(bl, idx);
}
for (int i = st[bl]; i <= ed[bl]; i++)
{
if (a[i] == x) rgt[bl][idx] = i;
if (a[i] == y) rgt[bl][idy] = i;
}
for (int i = ed[bl]; i >= st[bl]; i--)
{
if (a[i] == x) lft[bl][idx] = i;
if (a[i] == y) lft[bl][idy] = i;
}
}
inline bool exist(int l, int r, int x)
{
for (int i = l; i <= r; i++)
if (a[i] == x) return true;
return false;
}
inline void update(int l, int r, int x, int y)
{
int bl = bel[l], idx = id[bl][x], idy = id[bl][y];
if (!idx) return;
for (int i = st[bl]; i <= ed[bl]; i++) a[i] = val[bl][b[i]];
if (!exist(l, r, x)) return;
if ((!exist(st[bl], l - 1, x)) && (!exist(r + 1, ed[bl], x)))
{
if (idy) chg_col(l, r, x, y, 2);
else val[bl][idx] = y, id[bl][y] = idx, id[bl][x] = 0;
}
else chg_col(l, r, x, y, idy ? 1 : 0);
}
inline void modify(int l, int r, int x, int y)
{
if (x == y) return;
if (bel[l] == bel[r]) return update(l, r, x, y);
update(l, ed[bel[l]], x, y), update(st[bel[r]], r, x, y);
for (int i = bel[l] + 1; i <= bel[r] - 1; i++)
if (id[i][x])
{
if (id[i][y]) build(st[i], ed[i], x, y);
else val[i][id[i][x]] = y, id[i][y] = id[i][x], id[i][x] = 0;
}
}
inline int query(int l, int r, int x, int y)
{
int res = inf, lx = -inf, ly = -inf;
if (x == y)
{
#define check(l, r) for (int i = l; i <= r; i++) (a[i] = val[bel[i]][b[i]]) == x && (res = 0);
if (bel[l] == bel[r])
{
check(l, r);
return (res == inf ? -1 : res);
}
check(l, ed[bel[l]]) check(st[bel[r]], r)
for (int i = bel[l] + 1; i <= bel[r] - 1; i++)
if (id[i][x]) res = 0;
return (res == inf ? -1 : res);
#undef check
}
#define check(l, r) for (int i = l; i <= r; i++) \
a[i] = val[bel[i]][b[i]], \
(a[i] == x) && (chk_min(res, i - ly), lx = i), \
(a[i] == y) && (chk_min(res, i - lx), ly = i)
if (bel[l] == bel[r]) check(l, r);
else
{
check(l, ed[bel[l]]);
for (int i = bel[l] + 1; i <= bel[r] - 1; i++)
{
int idx = id[i][x], idy = id[i][y];
if (idx) chk_min(res, lft[i][idx] - ly);
if (idy) chk_min(res, lft[i][idy] - lx);
if (idx && idy && (dis(i, idx, idy) != inf)) chk_min(res, dis(i, idx, idy));
if (idx) lx = rgt[i][idx];
if (idy) ly = rgt[i][idy];
}
check(st[bel[r]], r);
}
return (res == inf ? -1 : res);
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
init();
while (m--)
{
int opt, l, r, x, y;
opt = read(), l = read(), r = read(), x = read(), y = read();
if (opt == 1) modify(l, r, x, y);
else write(query(l, r, x, y)), putc('\n');
}
flush();
return 0;
}