题目背景

2019 年 5 月 17 日，Ynoi2018 Day 2 的题目上传至洛谷公共题库。

2019 年 5 月 19 日，mrsrz 想出了[Ynoi2018]天降之物的序列分块做法，并尝试 AC 该题。

2019 年 5 月 21 日，在 lxl 略微放宽时限，加上各种玄学优化下，mrsrz 通过了此题（现在时限改回来了所以没希望了）。

过了若干日，mrsrz 发现该序列分块做法可以支持区间查询，和 lxl 讨论后，发现也可以做到区间修改。

2019 年 10 月，mrsrz 找到 disangan233 并告诉了他这个题。disangan233 收下了这个题并打算作为 MtOI2019 Extra Round 的 F 题。

2019 年 11 月 1 日，mrsrz 发现某个地方的某个比赛的某个题和该题有类似的地方。观察题解后发现了几乎一样的做法。然后这个原来的 F 题没了。

2019 年 11 月 2 日，MtOI2019 Extra Round 顺利进行。

2019 年 11 月 30 日，mrsrz 想起了这道题，决定将这道饱经风霜的题贡献至公共题库中。希望这道题，能对大家有所帮助。

by mrsrz

2019 年 11 月 30 日

Update：

2019 年 12 月 2 日，经 disangan233 同意，本题仍使用原来的题面。

2021 年 8 月 13 日，更新了 std，现在 std 的空间复杂度为 $O(n+m)$。

---

「俺、セツナは、お前を永遠に愛することちか！」
「我，Setsuna，发誓将会永远爱着你！」

「私の、あなたを永遠に愛することちかう！」
「我也是，发誓会永远爱着你！」

「歴史がかでもまた得た、ウェディングドレスてあみあをそ！」
「要是我们在其他的历史中再次相遇，那就披上婚纱再来一次吧！」

题目描述

Rinne 给了你一个数列 $a_1,a_2,\dots,a_n$，你需要依次执行 $m$ 个操作。

操作共有两种：

1. 给定 $l,r,x,y$，将 $a_l,a_{l+1},a_{l+2},\dots,a_r$ 中等于 $x$ 的数全部改成 $y$。

2. 给定 $l,r,x,y$，找到 $i,j$ 满足 $i,j\in[l,r]$ 且 $a_i=x,a_j=y$，并要求 $|i-j|$ 最小。求这个最小值。无解输出 $-1$。

输入格式

第一行两个正整数 $n,m$，表示序列长度和操作个数。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行五个正整数 $op,l,r,x,y$。若 $op=1$，表示修改操作。若 $op=2$，表示询问操作。$l,r,x,y$ 对应的含义见题目描述。

输出格式

对每个 $op=2$ 的操作，输出一行一个整数表示答案。

6 5
1 1 4 5 1 4
1 1 3 1 7
2 1 4 7 7
1 1 5 7 3
2 2 6 1 3
2 3 3 3 3

0
3
-1

提示

对于 $100\%$ 的数据，$1\leq n,m,a_i,x,y\leq 10^5$，$1\leq l\leq r\leq n$。

本题共有 $6$ 个子任务，每个子任务的限制如下：

子任务 $1$（$1$ 分）：保证对于任意操作，$l=1,r=n$。

子任务 $2$（$5$ 分）：$n,m\leq 50$。

子任务 $3$（$18$ 分）：$n,m\leq 2000$。

子任务 $4$（$7$ 分）：保证 $a_i,x,y\in\{1,2\}$。

子任务 $5$（$29$ 分）：保证当 $op=2$ 时，$x=y$。

子任务 $6$（$40$ 分）：没有特殊限制。

时间限制：$1.5\rm s$

空间限制：$512\rm MB$

Idea：nzhtl1477，mrsrz

Solution：mrsrz，nzhtl1477

Code：mrsrz

Data：mrsrz

Background：disangan233，mrsrz