时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
"我觉得这道题用线段树很好做啊"
arthalter信誓旦旦说道
于是他今天的犯唐额度又超标了.
你有一条长度为 n 的灯带,每个位置有一个颜色,记为 ai。
对于任意区间 [l,r],定义其颜色段数为:将该区间从左到右划分为若干个连续子段,使得每一段内所有位置颜色相同,且任意相邻两段的颜色不同,这些子段的数量即为颜色段数。
现在你需要处理 m 次操作,操作共有三种:
-
Cover l r c
表示将区间 [l,r] 内的所有位置颜色都修改为 c。
-
Reverse l r
表示将区间 [l,r] 内的颜色序列整体反转。
也就是说,操作后对于任意 i∈[l,r],原来位置 i 的颜色会移动到位置 l+r−i。
-
Query l r
表示询问当前区间 [l,r] 的颜色段数。
-
输入描述:
第一行两个整数 n,m,表示灯带长度和操作次数。
第二行 n 个整数 a1,a2,…,an,表示灯带初始时每个位置的颜色。
接下来 m 行,每行描述一个操作,格式为以下三种之一:
- Cover l r c
- Reverse l r
- Query l r
保证 1≤l≤r≤n。
- 对于 100% 的数据,1≤n,m≤200000
- 1≤ai,c≤10^9
输出描述:
对于每个 Query 操作,输出一行一个整数,表示对应区间的颜色段数。
示例1
输入
复制
8 6
1 1 2 3 3 2 2 4
Query 1 8
Reverse 3 6
Query 1 8
Cover 3 6 5
Query 1 8
Query 3 6
示例2
输入
复制
10 7
1 2 2 3 4 4 5 6 6 7
Query 1 10
Cover 4 8 2
Query 1 10
Reverse 2 9
Query 1 10
Query 3 7
Query 8 10