Can anyone discuss their approach for this question ?
Hint: For each element in each array, determine the range in which they are the maximum number. This can be accomplished in linear time using a stack.
Thanx that you provided hint…now i can think some more.
I did this using stock span, but after that I couldn’t figure out O(n) method to calculate all the values. Could you give some hint.
@domhieu : I figured out that we can determine the range in which an element is maximum but couldnt figure out what to do next. I meant how to calculate the contribution of the element for each K ?
for example if the array is 5 4 3 2 1 : contribution of 5 is 1 for every K(1<=K<=5), if the array was 4 5 3 2 1 contribution becomes 1 2 2 2 1, if the array was 1 2 5 4 3 contribution becomes 1 2 3 2 1 . Is there some pattern I am missing ?
@sarvagya3943 You’re heading in the right direction. Be careful calculating how many times an element contribute to a particular K though  it’s not necessarily 1 for every possible value of K. After that you might detect some pattern in which the use of a rangeupdating scheme might come in handy. I spent almost 2 days cracking, debugging and optimizing this problem and thoroughly enjoyed every aspect of it. Problem solving at its finest ! (y)
What was the real difference between the subtasks, other than the constraint on N.
My solution was in O(n) , but did not pass 2nd sub task.
@vibhor3gupta , mine solution is quite similar to yours. You got WA on some test cases because of overflow issues. Solution 1 which is similar to yours also gave me 40 points instead of the algorithm being O(n) due to overflow issues. But once after correcting the overflow issues, Solution 2 passed for 100 points.
Glitch in your code:
Since you are using prefix sum, the number you are adding in each iteration can be either positive or negative, also the limit of number being added or subtracted is unknown.
To correct this in your code add the lines
while (ak[i] <= 0)
a[i] += MOD;
if (ak[i] >= MOD)
a[i] %= MOD;
Similarly for array “bk”.
Also, the bigger glitch was regarding the modified array “a” and “b” which you formed.
a[i] += i; was fine, but you took mod with it which may have altered the values of a[i] desired, i.e. changing the maximum values affecting for array “l” and “r” and finally your answer.
(Example a[10^4] = 10^9 + 10^4; but once you take mod, it’s value decreases and it may not be detected in the desired window size for addition to array “ak”.
Here is a bit modified version of your code which passes for 100 points. Modified Code for AC
You can use spare table and range minimum query approach to get maximum on interval. And after smart approach you can skip half of an array while pre compute partial sums to get final answer. After all you will get something close to O(n * log n)
Here is my solution. https://www.codechef.com/viewsolution/9390323
Thanks for the clarification @likecs but overflow was never an issue ,the only issue was modifying the array A and B , before computing the ranges.
@likecs
Hey, If you could just explain what each of these lines signifies and what exactly it is that you are holding in your array k, it would be a great help.
k[1] += b[i];
k[m + 2] = b[i];
k[diff  m + 1] = b[i];
k[diff + 2] += b[i];
Thanks!
I solved this problem using Stack and Range updating with Fenwick Tree.
The approach was like this:
For both arrays , calculate these variations :
A=[4,1,9] , asum[k=1]=14
A=[4,9] , asum[k=2]=13
A=[9] , asum[k=3]=9
Means , for each value of k , we have to find sum of max of each window of size = k;
Then, do this for array B[] , like this:
B=[3,4,1] , bsum[k=1]=8
B=[4,4] , bsum[k=2]=8
B=[4] , bsum[k=3]=4
Now, finding the answer is very easy :
For k=1 , cout<<asum[1]*bsum[1];
For k=2 , cout<<asum[2]*bsum[2];
For k=3 , cout<<asum[3]*bsum[3];
Problem is solved.
To calculate asum[] and bsum[] arrays , the process is like this:
For each element in A[] , find next greater element to its left and right . In this range ,this
number is maximum. So , we will add this number to all possible ranges made by this interval
(Using Fenwick tree).
I’ll start with breaking down the original problem:

[C] = [A(+i)]_{(nx1)vert} x [B(+j)]_{(1xn)hori}
So, change the input A and B matrices accordingly. 
Consider max of each subrange in each of the matrices (new A and B). Lets say, at the moment, we are talking about subranges of length k. Now, each max of subrange of length k in matrix A will be multiplied to each max of subrange of length k in matrix B to contribute to the sum required for that k (kxk matrix in C).
The Solution (Do for both A as well as B):
 Find span (leftindex and rightindex after which a greater value occurs) of each element (i^{th}) of the matrix. Can be done using stacks in O(n) complexity. Prepare a field contrimax as rightindex  leftindex + 1. Prepare another field limit as min(i  leftindex, rightindex  i).
 Now, observe that the i^{th} element’s contribution to subrange of length 1 (ie k=1) is 1, subrange of length 2 is 2… until subrange of length limit; then it has a constant contribution uptil subrange of length contrimax  lim; and then it has a linearly decreasing contribution (to 1) till subrange of length contrimax. (Work out some examples). This also can be achieved in O(n) complexity by applying the marking algorithm (cannot come up with a better name :p) for adding a constant sum (here, the i^{th} element) from L_{i} to R_{i}.
Note: After marking the ranges for all elements, perform the summation operation twice to achieve the increasing/decreasing behavior.
Lets say we created two arrays of length n, namely increa for A and increb for B in the above process. Now, the multiplication of i^{th} element of increa with i^{th} element of increb is the solution for all ixi submatrices of C (ie F according to the question).
Handle the equality cases in Step 1 of the solution. Do all required operations in modular arithmetic.
Link for not so good code: link text