[MtOI2019] 手牵手走向明天
题目背景
2019 年 5 月 17 日，Ynoi2018 Day 2 的题目上传至洛谷公共题库。
2019 年 5 月 19 日，mrsrz 想出了[[Ynoi2018]天降之物](https://www.luogu.com.cn/problem/P5397)的序列分块做法，并尝试 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$ 的操作，输出一行一个整数表示答案。
输入输出样例
输入样例 #1
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
输出样例 #1
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