Background

Problem provider: Asada Shino.

As everyone knows, there are only zero times and countless times for cross-dressing.

Problem Description

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?

Input Format

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.

Output Format

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

10 4
3 3 3 3 2 3 3 3 2 2
Q 1 6 1
Q 1 6 0
R 8 8 2
Q 5 10 1

5
4
4

Hint

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