Problem1339--串联电路

1339: 串联电路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 138  Solved: 75
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有n个电源,编号为1~n,从左至右依次摆放,相邻的电源间用电线连接。连接在一起的电源构成一个连通段。初始时n个电源属于同一个连通段。
现在PIPI有3种操作:
D x:表示拿走编号为x的电源以及其连接相邻电源的电线。
Q x:询问编号为x的电源所属连通段的电源个数。若x已被拿走,则输出0。
R:将上一次拿走的电源放回,并恢复连接其相邻电源。
你需要处理这些操作。

Input

第一行输入两个正整数n,m,分别表示电源数量以及操作的次数。(n<=500000,m<=100000)
接下来m行,每行给出一个操作。 格式如题目描述所示。

Output

对于每个Q操作,输出一个答案。每个答案占一行。

Sample Input

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

Sample Output

1
0
2
4

Source/Category

中等