传统题 1000ms 256MiB

Tunnel Warfare

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

抗日战争在华北平原地区广泛爆发。这里有n个村庄,所有的村庄都排成一条线。除了两端的两个村庄,每个村庄都与两个相邻的村庄直接连接。在这场战争中会发生许多事件,可以分为以下三种情况: D x:第x个村庄被摧毁,与此连接的道路也会被摧毁。 Q x:陆军司令部要求查询与第x个村庄直接或间接连接的村庄数量,包括其自身。 R:修复最后被摧毁的村庄,与其连接的道路会被修复。

Format

Input

输入的第一行包含两个正整数 n 和 m(n、m ≤ 50000),表示村庄和事件的数量。接下来的 m 行,每一行表示一个事件。

Output

对于每个查询Q x,输出与第x个村庄直接或间接连接的村庄数量,包括其自身。

Samples

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
1
0
2
4

金牌集训营编程测试-2-20230716

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-7-16 18:30
结束于
2023-7-16 20:00
持续时间
1.5 小时
主持人
参赛人数
65