Part1. What did you think at the beginning
My initial idea was to think about what circumstances would be invisible.
in the case of\(i < j\)If you can read it directly\(j\)The slope and\(i\)The slope is comparison\(\frac{h_i}{i}\)judging the size relationship. So we need to modify the slope of a point with a single point. What we want to count is very complicated and we don’t figure it out, and then we don’t know what to use to maintain it.
Part 2. What is the correct solution
Reading the solution to the question, you can learn how to write a line segment tree. We define\(len\)Indicates the number of visible buildings in a section.
Abstract the question: the whole\(1-n\)In the interval of , each one that is greater than the previous one must be selected, and that is less than or equal to the previous one must not be selected. Find the final sequence length.
After observation, it was found that the interval is fixed, the answers to the large interval are merging, and the modification is simple, considering the maintenance of the segment tree.
There are two values in the segment tree. A maximum storage interval\(len\), a stored maximum slope value in the interval\(maxx\)。
Consider how to modify it? Modify directly,\(O(logn)\). The key is how to merge intervals (pushups).
Now consider two cell intervals,\(len\)and\(maxx\)It's something we can use directly. It can be found that the answer to the left interval can be directly inherited. Now we only need to consider the answer to the right interval.
So we're updatedtree[u].len=tree[ls].len+pushup2(tree[ls].maxx,rs,mid+1,rt), we found that it is indeed the answer of the left son who directly inherited it. The right son's answer is recursive. Why do you need to recursively calculate? Because the value on the left will actually have an impact on the answer on the right, the answer cannot be directly inherited, and the impact on the left must be calculated bit by bit. Pass a value\(lx\)It means that it needs to satisfy greater than\(lx\)Only then can you be seen. At this time, let’s look at the core classification discussion of pushup:
-
maxx<=lx,Finish -
a[l]>lx, you can prune branches at this time and return directly\(len_x\) -
l==r，return a[l]>lx - definition\(s_1\)is the left interval,\(s_2\)is the right interval.
- like
<= lx,return pushup(lx,s2,mid+1,r) - like
> lx,return tree[u].len-tree[ls].len+pushup(lx,s1,l,mid)
Let me tell you why it istree[u].len-tree[ls].lenInsteadtree[rs].len, because the update here is the first time, buttree[u]The update has been completed, and the right interval will be affected by the left interval. It is correct for us to cut this form.
Modify it\(O(logn^2)\)of.
Part3. What is the difference and how to solve it?
I didn't understand what I was going to do. I didn't expect that this kind of thing could be merged, and then it was maintained using a segment tree.
Solution: I have accumulated this way of thinking and solutions to this problem, and I feel that I can solve similar problems.
Part4. Encoding difficulties, errors caused
- No
- There are small places that make mistakes.
Part5. What are the harvests
After accumulating solutions to such similar problems, when you get this kind of modification query, you must first clarify what you are going to do, see what his equivalent problem is, then think about whether it can be merged, then make bold assumptions and carefully discuss!
Part6. Where is the main time spent
Understand the final subtraction and recursive pushup of the correct solution. This is still rare. You need to be knowledgeable to shorten the time.