Egon takes care of a garden with N apple trees. His responsibilities include two types of tasks:
fertilizing the trees and computing some statistics about them.
For fertilizing the trees he has several bottles of MegaBoostFertilizer, which, when treated on trees,
causes them to grow one centimeter up instantly. Every bottle has a limited capacity c_i, which determines
the number of trees it can be applied to. Moreover, for each bottle there is a minimal height h_i
of trees, which can be treated with it. Since Egon wants to have all his trees as big as possible, he always
applies the fertilizer to the c_i smallest trees chosen from the trees that are at least h_i centimeters
high.
When Egon computes statistics about trees he has to determine the number of trees whose height is
in some given interval. Egon is quite busy working in the garden, so he asked you to write a program,
that given the list of his tasks, computes the statistics for him.
The first line of the standard input contains two integers N and M denoting the number of trees in
Egon’s garden and the number of his tasks. The second line contains a sequence of N integers from
the range [1, N] describing the initial heights of the trees in centimeters. The following M lines
describe the tasks in chronological order. Each of those lines begins with a character t_i (t_i = F or
t_i = C), which describes the type of the task.
If t_i = F then two integers c_i and h_i follow. Such a line means that Egon applies a bottle of MegaBoostFertilizer to the c_i smallest trees among those trees that are at least h_i centimeters high. When
there are less than c_i trees of sufficient height, he applies the fertilizer to all such trees and discards
the bottle with some fertilizer remaining.
If t_i = C then two integers min_i and max_i follow. They denote that Egon has to compute the number
of trees whose height H is between mini and maxi centimeters (min_i≦ H ≦ max_i).
1 ≦ N, M ≦ 100000;
1 ≦ c_i ≦ N, 0 ≦ h_i ≦ 1000000000;
1 ≦ min_i ≦ max_i ≦ 1000000000.
For every task of type C, output one line containing the number of apple trees that have the required
height. The order of the results should conform to the order of type C tasks in the input.
5 7 1 3 2 5 2 F 2 1 C 3 6 F 2 3 C 6 8 F 2 1 F 2 2 C 3 5
3 0 5
Migrated from old NTUJ.
BOI2011 Competition Day 1
| No. | Testdata Range | Score |
|---|