#P5500. [LnOI2019] 真正的 OIer 从不女装
[LnOI2019] 真正的 OIer 从不女装
题目背景
题目提供者:朝田诗乃
众所周知,女装只有零次和无数次。
题目描述
给定一个长度为 的序列 。
有如下定义:若一个序列中所有数字都一样,那么这个序列被称作“诗乃序列”。
对于每次询问,给定 和 ,求序列 中左右端点都在 中的最长“诗乃序列”长度。
这题难倒了 Abbi。Abbi 决定女装。当 Abbi 女装时,序列会出现神奇的变化:它可以在询问的区间 中挑一个它喜欢的位置 ,将区间 和 分别翻转。
Abbi 想知道,最多进行 次女装后(可选择进行不足 次或不进行女装),能得到的最长的“诗乃序列”的长度是多少?
输入格式
第一行,、,表示序列长度和操作个数。
第二行, 个数,第个数表示序列初始值 。
接下来 行,每行描述一个操作,格式如下:
- :表示将区间 上的数字全部变成 。
- :表示询问在 中进行最多 次女装所能得到的最长“诗乃序列”长度。
注意:询问独立,即每次询问后会将序列复原,不实际执行反转操作。
输出格式
对于每个 Q 操作,输出询问答案。
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
提示
时空限制:1s/512MB。
数据范围:
- 对于 的数据,。
- 对于另外 数据,所有询问的 。
- 对于另外 数据,没有 R 操作。
- 对于 的数据,,,,。
特殊限制:对于后 的数据,保证能卡飞 ODT。
样例解释:
对于第一次询问,询问的区间为:
3 3 3 3 2 3
女装 次,将区间 和 分别翻转,得到:
3 3 3 3 3 2
此时可得到最长“诗乃序列”,长度为 。可以证明没有别的女装方法能得到更长的“诗乃序列”。
此后询问以此类推。
建议使用读入优化。