Problem

Submissions

Solution

New

Discuss

1

Difficulty: NINJA

Avg. time to solve

55 min

Success Rate

45%

Problem Statement

Suggest Edit

```
You have to find the maximum number of ways in which Kevin can buy the chocolates if he is allowed to choose boxes in random order.
```

```
You have to find the maximum number of ways in which Kevin can buy the chocolates if he is only allowed to choose the consecutive boxes.
```

```
There are ‘Q’ queries given to you and each query can be of two types:
0 I V
1 L R
The first type has 0 as a first character that represents this is an update query in which you have to update the number of chocolates in the “Ith” box to ‘V’.
The second type has 1 as a first character that represents this is a range query in which you have to find the maximum number of ways in which Kevin can buy the chocolates in the range [L, R] if he is allowed to choose boxes in any order.
```

```
1. There is no need to maximize the number of chocolates bought by Kevin.
2. Consider 1 based indexing for queries. There must be a single query of type 1.
3. You have to take the modulo with 10^9 + 7 as the result can be very large.
```

```
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain a single integer ‘N’ which denotes the number of chocolate boxes in the shop.
The second line of each test case contains ‘N’ space-separated integers which denote the number of chocolates in a particular box.
The third line of each test case will contain a single integer ‘Q’ which denotes the number of queries.
The next ‘Q’ lines contain three integers “0 I V” or “1 L R” in which ‘I’ represents the index whose value will have to be updated to ‘V’. ‘L’ and ‘R’ represent the inclusive range for which the result has been asked.
```

```
For each test case, print the result of all three subproblems in order such that:
In the first line, the result of subproblem 1 (FIRST) is printed.
In the second line, the result of subproblem 2 (SECOND) is printed.
In the third line, the result of each range query of type 1 is printed and each integer must be separated by a single space.
Output for every test case will be printed in a separate line.
```

```
You don’t need to print anything; It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 100
1 <= ARR[ i ] <= 10^5
1 <= Q <= 100
1 <= I, L, and R <= N
1 <= V <= 10^5
Where "ARR[i]” is the number of chocolates in the “i-th” box, ‘Q’ is the number of queries, and ‘I’, ‘V’, ‘L’, and ‘R’ are described in the Input format.
Time limit: 1 sec
```

```
1
4
2 3 5 8
2
0 1 3
1 1 3
```

```
3
2
3
```

```
In the first test case, the number of ways in which Kevin can buy the chocolates if he chooses boxes in any order is 3 ([2, 5, 8], [3], [2, 3, 5, 8]), if he chooses only consecutive boxes then answer is 2 ([2, 3, 5, 8] and [3]) and after updating the array answer for the range query is 3 ([3], [3], [3,3]).
```

```
2
1
12
4
0 1 2
1 1 1
0 1 3
1 1 1
3
3 1 3
2
0 2 3
1 1 3
```

```
1
1
0 1
3
2
7
```

```
In the second test case, Results for each subproblem are as follows:
FIRST :- [3], [3, 3], and [3].
SECOND :- [3], and [3]
THIRD :- [3], [3, 3], [3, 3], [3, 3, 3], [3], [3, 3], and [3].
```

Console