Given an array A of N (N<=10^6) elements. Here Ai denotes the height of ith plant. There are Q (Q<=10^6) queries of 3 types: 1. CUT h: Here for all plants with height greater than h ,cut them to height h. 2. GROW i x: Increase the height of ith plant by x (x<=10^6). 3. MAGIC y: Increase the height of all plants by y (y<=10^6).
For each query of type 1 , we have to print the total length of plants that is to be cut . Please suggest some approach to solve this problem.
You can build a segment tree for given array where each node of the tree will hold the sum of the plants extra length. And a normal variable to count the third type of query given it will apply for all the elements.
I would suggest to keep pairs in the tree nodes. First one for the ans you want, second one for the actual length.
You can solve this problem with segment tree over the possible height values. You start with at most N possible values. Every CUT and GROW query will give you at most Q different values. For the MAGIC query, given that it applies to the whole array, you can keep track of the original values by holding a cumulative increase.
You should have O(n+q) values. You can do a segment tree over these values and answer each query easily
This will help .