### PROBLEM LINK:

**Author:** Shivam Manchanda

**Tester:** Shubham Singhal

**Editorialist:** Shivam Manchanda

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

DP

### QUICK EXPLANATION:

Use dynamic programming to pre-compute Fun(r,k) for all 1≤r≤50000. Now during the input of operations, calculate how many operations are applied at each index. For every index B[i]=B[i]+ (no of operations[i] * (Fun(A[i],k))).

### EXPLANATION:

#### Computer P®

Let us maintain an array DP, where DP[i] represents minimum fibonacci numbers that sum-up to i. You can now make a recursive definition:

```
for(i from 1 to 50000)
{
if(i is fibonacci)
{
DP[i] = 1;
Store i;
}
else
{
for(j in all fibonacci less than i)
{
DP[i] = minimum of all(DP[i-j]+1);
}
}
}
```

NOTE: If you try to check all numbers (as j)less than i, you might get TLE. But as storing fibonacci numbers smaller than i will definitely get AC.

#### Applying operations

Take an array OPR, where OPR[i] represents number of operations on index i. Initialize this array with 0. Now, for every operation performed from *L* to *R*, do this:

```
OPR[l]++;
OPR[r+1]--;
```

After performing all operations, take a cumulative sum of the array from index 1 to N, as follows:

```
for(i from 1 to N)
OPR[i]+=OPR[i-1];
```

Finally, you have OPR ready.

#### Answering Queries

As, we have computed the number of operations on each index OPR and P®, thus query can be answered simply as:

```
B[x] = B[x] + ( OPR[x] * ( P[A[x]] less than k ? 1 : 0 ) );
```

### TIME COMPLEXITY

O(N+M+Q)

### ALTERNATIVE SOLUTION:

The part to compute number of operations applied can also be done using Segment Trees but in O(n*logn).

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

Author’s solution can be found here.

Tester’s solution can be found here.