UOJ Logo

NOI.AC

#10. 小x的城池

统计

作为国家的管理者,小 x 新开拓的有 $n$ 做城池,这 $n$ 座城池排成一条直线,依次编号为 $1 \sim n$,初始时对于所有 $i \in [1,n-1]$ 城市 $i$ 到城市 $i+1$ 有单向道路。

每个城市都有一个等级 A 或者 B,A 级市更高一些,所以按理来说应该拥有更多的人口。不过有的 A 级市可以通过道路到达人口更多的 B 级市,那么这个 A 级市就有被降级的危险,我们称这个 A 级市是危险的。

现在小 x 列出了一系列改造计划,希望你能实时跟进这些计划,并时刻告诉他有多少个 A 级城市是危险的。

改造计划有两种:

$\texttt{UPDATE x y}$: 人口迁移政策,把第 $x$ 个城市的人口修改为 $y$。

$\texttt{REVERSE l r}$: 道路修改计划,把第 $l$ 个城市到第 $r$ 个城市之间的道路全部翻转(每条道路改变朝向,而不是拿出一条链反过来接回去)。

对于每个计划,输出一行一个正整数表示修改之后危险的 A 级城市的数目。

输入格式

第一行两个正整数 $n, Q$ 表示城市数和询问数。

接下来 $n$ 行,每行一个整数和一个字符(只能是$\texttt{A,B}$) $P_i, c$,表示每个城市的人口和等级。

接下来 $Q$ 行,每行如下:

$\texttt{UPDATE x y}$

$\texttt{REVERSE l r}$

如题意表示一次改造。

输出格式

对于每个操作输出一行一个整数表示答案。

样例一

input

7 4
0 A
13 B
4 B
11 B
10 A
12 B
4 A
REVERSE 2 5
UPDATE 5 12
REVERSE 5 7
UPDATE 2 0

output

2
2
3
1

样例二

见样例数据下载。

限制与约定

本题采用捆绑测试,对于全部数据,$1 \leq N,Q \leq 10^5; 1 \leq x \leq n; 1 \leq l \leq r \leq n; 0 \leq P_i,y \leq 75.$

子任务编号 分值 $n, Q$ 约定
110$ \leq 10^3$
235$\leq 10^5$没有 $\texttt{REVERSE}$ 操作
335没有 $\texttt{UPDATE}$ 操作
420

时间限制:$4\texttt{s}$

空间限制:$233\texttt{MB}$

下载

样例数据下载