Description

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty. Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are: 1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away. 2. A range [a,b] is given (1 <= a <= b <= N), and everybody in that range of seats leaves. Please help Bessie count the total number of parties that are turned away over the course of the day.

m(m<=300,000)个操作。操作分2种:
1.A p,表示把编号最小的空着的长度为p的区间图上颜色。
2.L a b,表示把从ab的区间(包括端点)全部擦干净(没颜色还是没颜色)。
Q:有多少个操作1不能实现?

Input

 

* Line 1: Two space-separated integers, N and M.
* Lines 2..M+1: Each line describes a single event. It is either a line of the form “A p” (meaning a party of size p arrives) or “L a b” (meaning that all cows in the range [a, b] leave).

Output

 * Line 1: The number of parties that are turned away.

 

Sample Input

10 4
A 6
L 2 4
A 5
A 2
INPUT DETAILS: There are 10 seats, and 4 events. First, a party of 6 cows arrives. Then all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a party of 2.

Sample Output

1

OUTPUT DETAILS: Party #3 is turned away. All other parties are seated.

HINT

样例解释:
  首先将1~6图上颜色,再把2~4擦掉,这时不存在长度为5的空着的区间,该操作不能实现,跳过。最后把2~3图上颜色。所以不能实现的操作1有一个,即第三个操作。

Source

Gold

那天看到这题发现想不起来细节怎么做了花时间写了写

维护区间最长空闲和左区间最长空闲和右区间最长空闲即可

 

分类: 线段树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注