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
First:[l,l+m-1],[l+m,l+2m-1].....[l+(x-1)m,l+xm-1]
Second:[l+xm,r]
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.net/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.
I don't have one, but i found one
link
The first comment below tutorial QwQ
Maybe I can use a deque instead of segment tree. Then it will be O(n)
Deque is very slow,even slower than log(n)
But in complexcy it is better.
also optimize with handwriting in smaller constant
Knee new bee.
Please use $$$\LaTeX$$$.