文艺线段树
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

"我觉得这道题用线段树很好做啊"

arthalter信誓旦旦说道

于是他今天的犯唐额度又超标了.

你有一条长度为  的灯带,每个位置有一个颜色,记为 

对于任意区间 ,定义其颜色段数为:将该区间从左到右划分为若干个连续子段,使得每一段内所有位置颜色相同,且任意相邻两段的颜色不同,这些子段的数量即为颜色段数。

现在你需要处理  次操作,操作共有三种:

  • Cover l r c
    表示将区间  内的所有位置颜色都修改为 

  • Reverse l r
    表示将区间  内的颜色序列整体反转。
    也就是说,操作后对于任意 ,原来位置  的颜色会移动到位置 

  • Query l r
    表示询问当前区间  的颜色段数。



输入描述:

第一行两个整数 n,m,表示灯带长度和操作次数。

第二行 n 个整数 a1,a2,,an,表示灯带初始时每个位置的颜色。

接下来 m 行,每行描述一个操作,格式为以下三种之一:

  • Cover l r c
  • Reverse l r
  • Query l r

保证 1lrn

  • 对于 100% 的数据,1n,m200000
  • 1ai,c10^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

输出

复制
5
5
4
1
示例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

输出

复制
7
4
4
1
2