Background

On May 17, 2019, the problems of Ynoi2018 Day 2 were uploaded to the public problemset on Luogu.

On May 19, 2019, mrsrz came up with a sequence block-decomposition approach for [Ynoi2018]天降之物 and tried to get AC on that problem.

On May 21, 2019, with lxl slightly relaxing the time limit and with various “mysterious” optimizations, mrsrz passed the problem (the time limit has now been changed back, so there is no hope anymore).

After a few days, mrsrz found that this block-decomposition approach could support range queries. After discussing with lxl, they found that it could also handle range modifications.

In October 2019, mrsrz found disangan233 and told him about this problem. disangan233 accepted it and planned to use it as problem F of MtOI2019 Extra Round.

On November 1, 2019, mrsrz found that a certain problem from a certain contest had something similar to this one. After reading the editorial, he found an almost identical approach. Then the original problem F was gone.

On November 2, 2019, MtOI2019 Extra Round was held successfully.

On November 30, 2019, mrsrz remembered this problem and decided to contribute this weather-beaten problem to the public problemset. He hopes this problem can be helpful to everyone.

by mrsrz

November 30, 2019

Update:

On December 2, 2019, with disangan233’s consent, this problem still uses the original statement.

On August 13, 2021, the std was updated, and now the space complexity of std is $O(n+m)$.

「俺、セツナは、お前を永遠に愛することちか！」
「Me, Setsuna, swear that I will love you forever!」

「私の、あなたを永遠に愛することちかう！」
「Me too, I swear I will love you forever!」

「歴史がかでもまた得た、ウェディングドレスてあみあをそ！」
「If we meet again in another history, then put on a wedding dress and do it once more!」

Problem Description

Rinne gives you a sequence $a_1,a_2,\dots,a_n$. You need to perform $m$ operations in order.

There are two types of operations:

1. Given $l,r,x,y$, change all numbers equal to $x$ among $a_l,a_{l+1},a_{l+2},\dots,a_r$ into $y$.

2. Given $l,r,x,y$, find $i,j$ such that $i,j\in[l,r]$ and $a_i=x,a_j=y$, and require $|i-j|$ to be minimized. Output this minimum value. If there is no solution, output $-1$.

Input Format

The first line contains two positive integers $n,m$, representing the sequence length and the number of operations.

The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$.

The next $m$ lines each contain five positive integers $op,l,r,x,y$. If $op=1$, it is a modification operation. If $op=2$, it is a query operation. The meanings of $l,r,x,y$ are as described in the statement.

Output Format

For each operation with $op=2$, output one line with one integer, representing the answer.

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

Hint

For $100\%$ of the testdata, $1\leq n,m,a_i,x,y\leq 10^5$, $1\leq l\leq r\leq n$.

This problem has $6$ subtasks, with the following limits:

Subtask $1$ ($1$ point): Guaranteed that for any operation, $l=1,r=n$.

Subtask $2$ ($5$ points): $n,m\leq 50$.

Subtask $3$ ($18$ points): $n,m\leq 2000$.

Subtask $4$ ($7$ points): Guaranteed that $a_i,x,y\in\{1,2\}$.

Subtask $5$ ($29$ points): Guaranteed that when $op=2$, $x=y$.

Subtask $6$ ($40$ points): No special restrictions.

Time limit: $1.5\rm s$

Memory limit: $512\rm MB$

Idea: nzhtl1477, mrsrz.

Solution: mrsrz, nzhtl1477.

Code: mrsrz.

Data: mrsrz.

Background: disangan233, mrsrz.

Translated by ChatGPT 5