### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

Segment Tree

### PROBLEM:

This problem is essentially to ask you do the following queries:

Given some numbers between 1 and **5 * N**, find out the smallest 3 consecutive numbers not less than **P**, while the numbers are updated along time.

### EXPLANATION:

For this interval type of queries (here, refer to the “not less then **P**”), it is natural to think about segment trees.

In this problem, the specific problem is that finding out the smallest 3 consecutive numbers not less than **P**. We can first transform it to another alternative statement:

```
The smallest number which is not less than P and it has not been forbiden before.
```

where, a number is “forbidden” means that there are some numbers missing such that we can’t select 3 consecutive numbers starting from it.

More specifically, initially, we have all **5 * N - 2** numbers available except for the last 2 numbers, because there are not enough numbers after them. Then, when 3 numbers starting from **x** are selected by someone, i.e. **x, x+1, x+2** are selected, the 5 numbers **x-2, x-1, x, x+1, x+2** should be “forbidden”.

Therefore, this problem could be solved by a basic segment tree, which maintains the availability of all numbers, supports the query of minimum available number in an interval, and can set the availability of some specific number.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.

Tester’s solution can be found here.