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://mirror.codeforces.com/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>↵
↵
↵
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://mirror.codeforces.com/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>↵
↵
