提示: 欢迎访问OurACM平台。
Problem 1968 Twinkling lights III

Accept: 94    Submit: 259
Time Limit: 8000 mSec    Memory Limit : 131072 KB

Problem Description

Twinkling lights一直以来都很好玩的游戏。或许你还记得FZU1069 Twinkling lights 和FZU1420 Twinkling lights II。现在,Bluewind改变了一下游戏规则,游戏将变得更好玩。

N盏灯排成一行,编号1..N,起初的时候,所有的灯是开着的。Bluewind将执行M个操作,操作分成五种:

C x y,把编号从x到y的灯都关掉,原来关着的灯保持不变。

S x y,把编号从x到y的灯都开起来,原来开着的灯依旧开着。

A x y,让编号从x到y的灯都改变状态,即把原来开的灯关了,原来关了的灯开起来。

Q x y,查询编号从x到y中开着的灯的个数。

L x y,查询编号从x到y中最长连续开着的灯的个数。

Input

第一行两个整数N,M(1<=N,M<=500,000)表示有N盏灯,M个操作。

接下来M行,每行按指定格式给出一个操作,其中(1<=x<=y<=N)。

Output

对于每条Q查询操作和L查询操作,输出相应的结果。

Sample Input

10 5 C 2 8 S 5 7 A 1 10 Q 1 10 L 1 10

Sample Output

4 3

Source

Contest for 2010 lecture II

Submit  Back  Status  Discuss