My first problem.
Difference between en3 and en4, changed 1,441 character(s)
Hello everyone,↵

As the title suggests, this is my first problem on Codeforces, and it's a medium to medium-hard challenge. I'm preparing this because I'm about to become my school's coach. If you have some time, I'd greatly appreciate it if you could take a look and provide me with some feedback.↵

Thank you! Love you all <3.↵

https://codeforces.net/contestInvitation/ccca44d49a984409344ede5f912629800ea6e003↵


P/S : I hate to say this as you've probably heard this a lot C:, but I apologize for my poor use of English in the problem statement. C: 


Solution:↵

<spoiler summary = "Tutorial 1">↵
   You can process queries of type 3 offline. The trick is not to go forward and adding new element, but go backward and delete element. This can be done in $O(N log N^2)$, or in $O(N log N)$ using walk on segment tree.↵
   </n>↵


   Query of type 1,2,4 can be processed using segment tree with lazy propagation.↵
   </n>↵


   Query of type 2 can be broken down to this : $a_p += (p - l + 1)*x <=> a_p += (p + 1)*x - l*x$.↵


   </n> You can use a different segment tree to store the sum of $x$, then $-l*x$ can be trivially stored. ↵

   But there's still query of type 3 that may potentially affect the sum $l..r$. So our segment tree↵
    shouldn't store the sum of elements from $l...r$ $(a_l + a_{l + 1} + ... + a_r)$ , but the sum of the whole range $l$..$r$, regardless of whether this whole range has been fully filled with element or not. You will need an additional $cnt$ array to store the number of added elements, to calculate $(p + 1)*x - l*x$ ↵

   </n> For query of type 1, you need an "override" lazy propagation array.↵


   </n> The overall time complexity will be $O(N log N)$ or $O(N log ^2 N)$, both can comfortably fit in 1s runtime.↵
      ↵
</n> Space complexity $O(N log N)$↵
</spoiler>↵

<spoiler summary = "Tutorial 2">↵
My friends have tried and this can actually be solved with a $splay$ $tree$. I don't really know how to do it :>↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English peacebringer167 2024-06-27 12:27:07 1441 Tiny change: 'y.\n\n </n> Note that' -> 'y.\n\n Note that'
en3 English peacebringer167 2024-06-26 17:53:32 1 Tiny change: '9800ea6e00\n\n\nP/S ' -> '9800ea6e003\n\n\nP/S '
en2 English peacebringer167 2024-06-26 17:53:21 1 Tiny change: '9800ea6e003\n\n\nP/S ' -> '9800ea6e00\n\n\nP/S '
en1 English peacebringer167 2024-06-26 16:09:43 576 Initial revision (published)