【HDU 5575】Discover Water Tank

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5575
神犇题解:http://blog.csdn.net/qq_19592437/article/details/50252111
中文题面:https://ly.men.ci/problem/199

解题报告

这题我们可以用左偏树+并查集什么的
不过感觉分治更好写吧?

考虑$solve(l,r)$表示区间$(l,r]$的最优解
那么找出其中最高的挡板设为$x$,之后分两种情况讨论

  1. 区间水位低于$x$,那么我们分治$solve(l,x-1)+solve(x+1,r)$即可
  2. 区间水位高于$x$,那么我们搞一个前缀和就好

总的时间复杂度:$O(n \log n)$

50 thoughts to “【HDU 5575】Discover Water Tank”

  1. Hey! I could have sworn I’ve been to this website before but after browsing through some of the post I realized it’s new to me.
    Anyways, I’m definitely glad I found it and I’ll be
    bookmarking and checking back frequently!

  2. Having read this I believed it was extremely informative.

    I appreciate you taking the time and effort to put
    this informative article together. I once again find myself personally
    spending a lot of time both reading and commenting.
    But so what, it was still worth it!

  3. I feel this is among the such a lot significant information for me.
    And i am glad studying your article. However should statement on some basic things, The site style
    is great, the articles is in point of fact excellent : D.
    Excellent task, cheers

  4. Hi there just wanted to give you a quick heads up and let you know a few of the pictures aren’t
    loading correctly. I’m not sure why but I think its a linking
    issue. I’ve tried it in two different browsers and both show the same results.

  5. Appreciating the commitment you put into your site and detailed information you provide.

    It’s great to come across a blog every once in a
    while that isn’t the same out of date rehashed information. Great read!
    I’ve saved your site and I’m including your RSS feeds to
    my Google account.

  6. you’re in reality a good webmaster. The website loading pace is incredible.
    It sort of feels that you are doing any unique trick.
    Moreover, The contents are masterwork. you have performed a magnificent process on this subject!

  7. When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get several e-mails
    with the same comment. Is there any way you can remove people from
    that service? Thank you!

  8. Have you ever considered creating an e-book or guest authoring
    on other websites? I have a blog centered on the same subjects you discuss and
    would really like to have you share some stories/information.
    I know my viewers would value your work. If you are even remotely interested, feel free to shoot me an e-mail.

  9. Hello there, just became aware of your blog through Google, and found that
    it is really informative. I am going to watch out for brussels.
    I’ll be grateful if you continue this in future. Lots of
    people will be benefited from your writing. Cheers!

  10. My spouse and I stumbled over here different web address and thought I might as well check things out.
    I like what I see so now i’m following you.
    Look forward to checking out your web page repeatedly.

  11. I’ve been exploring for a bit for any high-quality articles or weblog posts on this sort of space .

    Exploring in Yahoo I finally stumbled upon this web site.
    Studying this information So i am happy to express that
    I have an incredibly good uncanny feeling I discovered exactly what I needed.
    I such a lot no doubt will make sure to do not put out of your mind this site and provides it a glance regularly.

  12. Right here is the right website for anybody who would like to find out about
    this topic. You understand so much its almost hard to argue with you (not that I really would want to…HaHa).
    You certainly put a new spin on a subject that’s been written about for decades.

    Excellent stuff, just wonderful!

  13. Somebody essentially assist to make significantly articles
    I would state. This is the first time I frequented your web page
    and thus far? I surprised with the analysis you made to create this actual submit incredible.

    Magnificent job!

  14. Howdy very cool blog!! Man .. Excellent .. Wonderful .. I’ll bookmark your web site and take the feeds
    additionally? I am glad to seek out numerous useful info right here in the
    submit, we want develop more techniques in this regard, thank you for sharing.
    . . . . .

  15. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4
    year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear. She never wants to go back!

    LoL I know this is totally off topic but I had to tell someone!

  16. I’m amazed, I must say. Seldom do I come across a blog that’s both equally educative and
    interesting, and without a doubt, you’ve hit the nail on the head.
    The problem is something not enough folks are speaking intelligently about.
    I’m very happy that I found this in my search for something regarding this.

  17. Greate pieces. Keep posting such kind of information on your site.
    Im really impressed by your site.
    Hello there, You’ve performed an incredible job. I’ll certainly digg it and
    individually recommend to my friends. I am confident they will be benefited from this site.

  18. You’re so cool! I don’t think I’ve read anything like this before.
    So good to find someone with genuine thoughts on this subject matter.
    Seriously.. thanks for starting this up. This website is something that’s needed on the web, someone with some originality!

  19. We are a group of volunteers and opening a new
    scheme in our community. Your site offered us with valuable info
    to work on. You’ve done an impressive job and our whole community
    will be thankful to you.

  20. Does your site have a contact page? I’m having a tough time locating it but, I’d like to send
    you an e-mail. I’ve got some creative ideas for your blog you might be interested in hearing.
    Either way, great website and I look forward to seeing it expand
    over time.

  21. Hi there! Would you mind if I share your blog with my facebook group?
    There’s a lot of folks that I think would really appreciate your content.

    Please let me know. Thanks

  22. Hi, I do believe this is an excellent site.
    I stumbledupon it 😉 I’m going to revisit yet again since I saved as a favorite it.
    Money and freedom is the best way to change, may you be rich and continue to
    help other people.

  23. Nice post. I used to be checking constantly this weblog and I am impressed!
    Extremely helpful information specifically the last part 🙂
    I deal with such info much. I was looking for this particular information for a very long time.
    Thank you and good luck.

  24. Awesome blog you have here but I was wanting to know if you knew
    of any forums that cover the same topics talked about here?

    I’d really love to be a part of group where I can get feed-back from other experienced
    individuals that share the same interest. If
    you have any suggestions, please let me know. Thanks!

发表评论

电子邮件地址不会被公开。 必填项已用*标注