P5500 [LnOI2019] A Real OIer Never Cross-dresses

Problem provider: Asada Shino. As everyone knows, there are only zero times and countless times for cross-dressing.

Given a sequence $a$ of length $n$. There is the following definition: if all numbers in a sequence are the same, then this sequence is called a “Shino sequence”. For each query, given $l$ and $r$, find the maximum length of a “Shino sequence” in $a$ whose **both endpoints are within $[l,r]$**. This problem stumped Abbi. Abbi decided to cross-dress. When Abbi cross-dresses, the sequence undergoes a magical change: it can choose a position $p$ that it likes **within the query interval $[l,r]$**, and **separately** reverse the intervals $[l,p]$ and $(p,r]$. Abbi wants to know: after cross-dressing at most $k$ times (you may choose to do fewer than $k$ times, or not cross-dress at all), what is the maximum possible length of a “Shino sequence” that can be obtained?

The first line contains $n$ and $m$, representing the sequence length and the number of operations. The second line contains $n$ numbers, where the $i$-th number is the initial value $a_i$. The next $m$ lines each describe an operation in the following format: 1. $R$ $l$ $r$ $x$: set all numbers in the interval $[l,r]$ to $x$. 2. $Q$ $l$ $r$ $k$: query the maximum length of a “Shino sequence” that can be obtained by cross-dressing at most $k$ times within $[l,r]$. **Note: Queries are independent. That is, after each query, the sequence is restored; the reversal operations are not actually applied.**

For each $Q$ operation, output the answer to the query.

**Time and memory limits**: 1s / 512MB. **Constraints:** - For $20\%$ of the testdata, $1 \le n,m \le 100$. - For another $10\%$ of the testdata, all queries have $k=0$. - For another $10\%$ of the testdata, there are no $R$ operations. - For $100\%$ of the testdata, $1 \le n,m \le 200000$, $0 \le k \le 1000$, $1 \le a_i,x \le 10^9$, $1 \le l \le r \le n$. Special restriction: for the last $80\%$ of the testdata, it is guaranteed that ODT can be hacked. **Sample explanation:** For the first query, the queried interval is: ``` 3 3 3 3 2 3 ``` Cross-dress once, and reverse $[1,4]$ and $[5,6]$ separately, obtaining: ``` 3 3 3 3 3 2 ``` At this time, the longest “Shino sequence” has length $5$. It can be proven that no other way of cross-dressing can produce a longer “Shino sequence”. Subsequent queries proceed similarly. **It is recommended to use fast input.** Translated by ChatGPT 5