 # OPRTNS - EDITORIAL

Practice

Contest

Author: Shivam Manchanda

Tester: Shubham Singhal

Editorialist: Shivam Manchanda

EASY-MEDIUM

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];
``````

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 ) );
``````

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.

//