D. The Grim Treaper SOLUTION

D. The Grim Treaper Algorithms Thread Treaps Contest

Happy Halloween! Farmer John is rather weary: he has lots of harvesting still unfinished, and his Deere sweet tractor just broke down, so he must finish the harvesting with nothing more than his scythe. He is rather depressed knowing the total amount of harvesting he has left. To make things even worse, Bessie and friends don’t know how to use a toilet, so they keep leaving… fertilizer… all over the grass, causing the wheat to grow even more! So much reaping of wheat needs to be done! How grim!
Initially, FJ has n blades of grass numbered 1..n in a row. Initially blade i has height ai. q times, one of the following will happen:
1. FJ will slice his scythe from l to r at height h, cutting all blades from l to r that are strictly longer than height h to height h.
2. FJ will transplant range l..r of his field to the end of the field. He will move all grass blades forwards so, in total, positions 1..n are still occupied after this operation.
3. Bessie and friends will take a dump on blades of grass from l to r. Each of them will grow by x units where x is the stinkiness of the… fertilizer.
After each operation, Farmer John needs to know how much work he has left to do. In particular, he would like to know the sum of heights of all blades of grass.
Input
The first line will contain two integers n and q: the number of blades of grass, and the number of events. (1≤n,q≤3∗105)
The second line will contain n integers: the initial heights of grass blades. (1≤ai≤106).
The following q lines will describe each query, and be of one of the following forms:
– 1 l r h. In this case 1≤l≤r≤n and 1≤h≤109.
– 2 l r. In this case 1≤l≤r≤n.
– 3 l r x. In this case 1≤l≤r≤n and 1≤x≤105.
Note that grass may grow to more than 2∗109 units.
Output
After each query, print a single line describing the total height of all blades of grass after that query.
Examples
inputCopy
3 3
125987 264237 288891
3 2 3 30851
2 2 3
3 1 2 88689
outputCopy
740817
740817
918195
inputCopy
5 5
3 3 1 8 7
1 4 5 9
2 1 3
3 1 2 4
2 2 5
3 3 3 5
outputCopy
22
22
30
30
35

Related :

Related :

Leave a Comment