### MagicSpark's blog

By MagicSpark, history, 18 months ago,

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.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.

• +24

 » 18 months ago, # |   +8 I don't have one, but i found onelinkThe first comment below tutorial QwQ
•  » » 18 months ago, # ^ |   +5 Maybe I can use a deque instead of segment tree. Then it will be O(n)
•  » » » 17 months ago, # ^ |   -12 Deque is very slow,even slower than log(n)
•  » » » » 17 months ago, # ^ |   0 But in complexcy it is better.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 also optimize with handwriting in smaller constant
 » 17 months ago, # |   +5 Knee new bee.
 » 11 months ago, # |   +15 Please use $\LaTeX$.