[LnOI2019]真正的OIer从不女装

题目背景

题目提供者:朝田诗乃 众所周知,女装只有零次和无数次。

题目描述

给定一个长度为$n$的序列$a$。 有如下定义:若一个序列中所有数字都一样,那么这个序列被称作“诗乃序列”。 对于每次询问,给定$l$和$r$,求序列$a$中**左右端点都在$[l,r]$中**的最长“诗乃序列”长度。 这题难倒了Abbi。Abbi决定女装。当Abbi女装时,序列会出现神奇的变化:它可以**在询问的区间$[l,r]$中**挑一个它喜欢的位置$p$,将区间$[l,p]$和$(p,r]$**分别**翻转。 Abbi想知道,**最多**进行$k$次女装后(可选择进行不足k次或不进行女装),能得到的最长的“诗乃序列”的长度是多少?

输入输出格式

输入格式


第一行,$n$、$m$,表示序列长度和操作个数。 第二行,$n$个数,第$i$个数表示序列初始值$a_i$ 接下来$m$行,每行描述一个操作,格式如下: 1、$R$ $l$ $r$ $x$:表示将区间$[l,r]$上的数字全部变成$x$。 2、$Q$ $l$ $r$ $k$:表示询问在$[l,r]$中进行最多$k$次女装所能得到的最长“诗乃序列”长度。 **注意:询问独立,即每次询问后会将序列复原,不实际执行反转操作。**

输出格式


对于每个Q操作,输出询问答案。

输入输出样例

输入样例 #1

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

输出样例 #1

5
4
4

说明

**时空限制:**$1s/512MB$。 **数据范围:** 对于20%的数据,$1 ≤ n,m ≤ 100$ 对于另外10%数据,所有询问的$k=0$。 对于另外10%数据,没有R操作。 对于100%的数据,$1≤n,m≤200000$,$0≤k≤1000$,$1≤a_i,x≤10^9$,$1≤l≤r≤n$ 特殊限制:对于后80%的数据,保证能卡飞ODT。 **样例解释:** 对于第一次询问,询问的区间为: 3 3 3 3 2 3 女装1次,将区间$[1,4]$和$[5,6]$分别翻转,得到: 3 3 3 3 3 2 此时可得到最长“诗乃序列”,长度为5。可以证明没有别的女装方法能得到更长的“诗乃序列”。 此后询问以此类推。 **建议使用读入优化**