When I am solving 1197D,I didn't see m<=10 and then I find a solution that can solve m<=n<=3e5
Here is my solution:
The range [l,r] is equal to [l,l+m-1],[l+m,l+2m-1]....[l+xm,r]
then we will enumeration the value of l+xm.
We consider every reminder(from 0 to m-1) of position module m and solve them independently.
When we are solving each of the reminders,we have v[i]-->the value of the ith range(from the ith position fits the reminder to the next),then we will consider the value of two parts
We can use segment tree to get the max prefix sum of [l+mx,l+(m+1)x-1],then it's the second part.
When we are solveing the first part,we need to find the min value of the prefix sum of v[i].
This can also be done using segment tree.
Then the answer for each l+xm is First+Second-k.
Here is my submission https://codeforces.com/contest/1197/submission/57841454
The final answer is the maximum of them.
Overall complexy O(n log n) with big constants
I wanna know if there are better solutions.
If you have,please share under this blog.