TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

陳棒跟他心愛的 wifi 正在玩好玩的遊戲 >//////<

一開始有一個很大的區間,區間中的每一項都是狀態 $1$。

接下來有很多操作,總共有三種操作。

  1. 操作 "TURN A B",把編號 $A$ 至編號 $B$ 之間的每一項狀態都 $+1$,如果有任一項原本是狀態 $3$,則操作完後他會回到狀態 $1$。
  2. 操作 "RESET A B",把編號 $A$ 至編號 $B$ 之間的每一項都變回狀態 $1$。
  3. 操作 "COUNT A B",計算編號 $A$ 至編號 $B$ 之間中共有幾項在狀態 $1$。

Input Format

輸入的第一行有兩個正整數 $N$ 和 $M$,分別代表區間大小以及操作數量。
接下來有 $M$ 行,每一行都是其中一種操作(請見題目敘述部分)。

$1\leq N,M\leq 1,000,000$,且 $1\leq A\leq B\leq N$

Output Format

對於每次 COUNT 操作,請輸出一行,包含一個數字,代表計算結果。

Sample Input 1

5 5
TURN 1 3
COUNT 1 5
RESET 2 4
TURN 3 5
COUNT 2 5

Sample Output 1

2
1

Hints

Problem Source

NEOJ Problem 257

東方神秘力量

Subtasks

No. Testdata Range Constraints Score
1 0 $N, M\leq 5,000$ 20
2 1 $N, M > 5,000$ 且不包含 RESET 操作 20
3 2~3 $N, M\leq 500,000$ 40
4 4 無額外限制 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 65536 1
1 5000 262144 65536 2
2 5000 262144 65536 3
3 5000 262144 65536 3
4 5000 262144 65536 4