Lakh's blog

By Lakh, history, 6 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This will help .