TOJ习题：《数据结构》-邓俊辉-清华大学1

A1.1.范围查询(Range)

Descriptioin

Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are

asked to count the points lying inside.

Input

The first line contains two integers: n (size of S) and m (the number of queries).

The second line enumerates all the n points in S.

Each of the following m lines consists of two integers a and b and defines an query

interval [a, b].

4 6

7 12

Output

0

3

Restrictions

0 <= n, m <= 5 * 10^5

For each query interval [a, b], it is guaranteed that a <= b.

Points in S are distinct from each other.

Coordinates of each point as well as the query interval boundaries a and b are

第一行包括两个整数：点的总数 n，查询的次数 m。

第二行包含 n 个数，为各个点的坐标。

以下 m 行，各包含两个整数：查询区间的左、右边界 a 和 b。

输出

对每次查询，输出落在闭区间[a, b]内点的个数。

样例

见英文题面

限制

0 ≤ n, m ≤ 5×10

5

A1.2.祖玛(Zuma)

Description

Let's play the game Zuma!

colored but no three adjacent ones are allowed to be with a same color. You can then

insert beads one by one into the sequence. Once three (or more) beads with a same

color become adjacent due to an insertion, they will vanish immediately.

Note that it is possible for such a case to happen for more than once for a single

insertion. You can't insert the next bead until all the eliminations have been done.

Given both the initial sequence and the insertion series, you are now asked by the fans

to provide a playback tool for replaying their games. In other words, the sequence of

beads after all possible eliminations as a result of each insertion should be calculated.

Input

The first line gives the initial bead sequence. Namely, it is a string of capital letters from

The following n lines tell all the insertions in turn. Each contains an integer k and a

Specially, "-" stands for an empty sequence.

Example

Input

ACCBA

5

1 B

0 A

2 B

4 C

0 A

Restrictions

0 <= n <= 10^4

0 <= length of the initial sequence <= 10^4

Time: 2 sec

Memory: 256 MB

Hints

List

描述

祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其

中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。

一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发

第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，不同的字母表

示不同的颜色。

第二行是一个数字 n，表示整个回放过程共有 n 次操作。

接下来的 n 行依次对应于各次操作。每次操作由一个数字 k 和一个大写字母 Σ 描述，以空

格分隔。其中，Σ 为新珠子的颜色。若插入前共有 m 颗珠子，则 k ∈ [0, m]表示新珠子嵌

入之后（尚未发生消除之前）在轨道上的位序。

输出

输出共 n 行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。

如果轨道上已没有珠子，则以“-”表示。

样例