#3050. [Usaco2013 Jan]Seating

[Usaco2013 Jan]Seating

题目描述

给你一个长度为 nn 的空白序列,要求支持这样 mm 次操作:

  • A p 表示把编号最小的空着的长度为 pp 的区间涂上颜色,假如无法操作则不操作。
  • L l r 表示把区间 [l,r][l,r] 全部擦干净(没颜色还是没颜色)。

求问,有多少个操作 11 无法完成。

输入格式

第一行两个数 nnmm ,用空格隔开。

接下来 mm 行,每行一个操作,格式如题目描述。

输出格式

一行一个数,即操作 11 无法完成的次数。

样例输入

10 4
A 6
L 2 4
A 5
A 2

样例输出

1

样例说明

首先将 [1,6][1,6] 涂上颜色,再把 [2,4][2,4] 擦掉,这时不存在长度为 55 的空着的区间,第三个操作不能实现,跳过。最后把 [2,3][2,3] 涂上颜色。所以不能实现的操作 11 有一个,即第三个操作。

数据规模与约定

1n5×1051 \le n \le 5\times 10^51m3×1051 \le m \le 3\times 10^5

题目来源

USACO 2013 Jan Gold