1

# Boxes and chocolates

Difficulty: NINJA
Avg. time to solve
55 min
Success Rate
45%

Problem Statement
Suggest Edit

#### FIRST:

``````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.
``````

#### SECOND:

``````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.
``````

#### THIRD:

``````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.
``````

#### Note:

``````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.
``````
##### Input Format:
``````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.
``````
##### Output Format:
``````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.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````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
``````
##### Sample Input 1:
``````1
4
2 3 5 8
2
0 1 3
1 1 3
``````
##### Sample Output 1
``````3
2
3
``````
##### Explanation of sample input 1:
``````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]).
``````
##### Sample Input 2:
``````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
``````
##### Sample Output 2:
``````1
1
0 1
3
2
7
``````
##### Explanation for sample input 2:
``````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