#P5500. [LnOI2019] 真正的 OIer 从不女装

[LnOI2019] 真正的 OIer 从不女装

题目背景

题目提供者:朝田诗乃

众所周知,女装只有零次和无数次。

题目描述

给定一个长度为 nn 的序列 aa

有如下定义:若一个序列中所有数字都一样,那么这个序列被称作“诗乃序列”。

对于每次询问,给定 llrr,求序列 aa左右端点都在 [l,r][l,r]的最长“诗乃序列”长度。

这题难倒了 Abbi。Abbi 决定女装。当 Abbi 女装时,序列会出现神奇的变化:它可以在询问的区间 [l,r][l,r]挑一个它喜欢的位置 pp,将区间 [l,p][l,p](p,r](p,r] 分别翻转。

Abbi 想知道,最多进行 kk 次女装后(可选择进行不足 kk 次或不进行女装),能得到的最长的“诗乃序列”的长度是多少?

输入格式

第一行,nnmm,表示序列长度和操作个数。

第二行,nn 个数,第ii个数表示序列初始值 aia_i

接下来 mm 行,每行描述一个操作,格式如下:

  1. RR ll rr xx:表示将区间 [l,r][l,r] 上的数字全部变成 xx
  2. QQ ll rr kk:表示询问在 [l,r][l,r] 中进行最多 kk 次女装所能得到的最长“诗乃序列”长度。

注意:询问独立,即每次询问后会将序列复原,不实际执行反转操作。

输出格式

对于每个 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。

数据范围:

  • 对于 20%20\% 的数据,1n,m1001 ≤ n,m ≤ 100
  • 对于另外 10%10\% 数据,所有询问的 k=0k=0
  • 对于另外 10%10\% 数据,没有 R 操作。
  • 对于 100%100\% 的数据,1n,m2000001≤n,m≤2000000k10000≤k≤10001ai,x1091≤a_i,x≤10^91lrn1≤l≤r≤n

特殊限制:对于后 80%80\% 的数据,保证能卡飞 ODT。

样例解释:

对于第一次询问,询问的区间为:

3 3 3 3 2 3

女装 11 次,将区间 [1,4][1,4][5,6][5,6] 分别翻转,得到:

3 3 3 3 3 2

此时可得到最长“诗乃序列”,长度为 55。可以证明没有别的女装方法能得到更长的“诗乃序列”。

此后询问以此类推。

建议使用读入优化。