【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)$

100 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!

  25. It’s really a great and useful piece of information. I’m satisfied that you
    simply shared this useful information with us. Please keep us informed like this.
    Thanks for sharing.

  26. Hey there! I know this is kinda off topic however , I’d figured I’d ask.

    Would you be interested in trading links or maybe
    guest authoring a blog post or vice-versa? My site discusses a lot of
    the same subjects as yours and I believe we could greatly benefit from each other.
    If you happen to be interested feel free to shoot me an email.

    I look forward to hearing from you! Excellent blog by the way!

  27. Thank you a bunch for sharing this with all people you actually understand
    what you’re talking about! Bookmarked. Kindly also visit
    my website =). We can have a hyperlink exchange agreement between us

  28. It is perfect time to make some plans for the
    longer term and it is time to be happy. I’ve learn this post and if
    I may I want to suggest you few fascinating issues or suggestions.
    Perhaps you could write subsequent articles referring to this
    article. I want to read more issues approximately it!

  29. Thanks for one’s marvelous posting! I quite enjoyed reading it,
    you might be a great author. I will always bookmark your blog and definitely will come back at some point.
    I want to encourage one to continue your great
    job, have a nice morning!

  30. Thank you, I’ve recently been looking for info approximately this topic
    for a while and yours is the greatest I’ve came
    upon so far. However, what concerning the bottom line? Are you positive
    in regards to the source?

  31. I think this is one of the most vital information for
    me. And i’m glad reading your article. But should remark on some general things, The
    site style is perfect, the articles is really great : D.

    Good job, cheers

  32. I like the valuable info you provide to your articles.
    I’ll bookmark your blog and test once more right here frequently.
    I am quite certain I will learn plenty of new stuff right here!
    Good luck for the next!

  33. It’s actually very complicated in this full of activity life to
    listen news on Television, therefore I just use web for that reason, and get the latest
    news.

  34. Hey there would you mind sharing which blog platform you’re
    working with? I’m going to start my own blog soon but I’m
    having a hard time selecting between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design seems different then most blogs and I’m looking for
    something unique. P.S Sorry for getting off-topic but I
    had to ask!

  35. Hi there very cool blog!! Man .. Excellent ..
    Amazing .. I’ll bookmark your blog and take the feeds also?
    I am happy to find so many useful information here within the submit, we’d like work out more techniques on this regard,
    thank you for sharing. . . . . .

  36. Hey there! This is kind of off topic but I need some guidance from an established blog.
    Is it difficult to set up your own blog? I’m not very techincal but I can figure things out pretty fast.
    I’m thinking about creating my own but I’m not sure where to start.

    Do you have any tips or suggestions? Cheers

  37. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored material stylish.
    nonetheless, you command get bought an nervousness over
    that you wish be delivering the following. unwell unquestionably come more formerly again as
    exactly the same nearly very often inside case you shield
    this increase.

  38. With havin so much content do you ever run into any issues of plagorism or copyright infringement?
    My site has a lot of unique content I’ve either written myself
    or outsourced but it appears a lot of it is popping it up all over the web without my
    agreement. Do you know any methods to help prevent content from being
    ripped off? I’d certainly appreciate it.

  39. I’m truly enjoying the design and layout of your website.

    It’s a very easy on the eyes which makes it much more enjoyable for me to come
    here and visit more often. Did you hire out a designer to create your
    theme? Exceptional work!

  40. Terrific work! This is the kind of information that are meant to be shared across the web.
    Shame on Google for not positioning this put
    up higher! Come on over and consult with my site .

    Thanks =)

  41. Hmm it appears like your website ate my first comment (it was super long)
    so I guess I’ll just sum it up what I submitted and say, I’m thoroughly
    enjoying your blog. I too am an aspiring blog blogger but I’m
    still new to everything. Do you have any suggestions for newbie blog writers?
    I’d definitely appreciate it.

  42. I just like the helpful info you supply to your articles.
    I’ll bookmark your weblog and test again right here regularly.
    I’m somewhat sure I’ll be informed lots of new stuff pproper
    right here! Best of luck ffor the next!

  43. Hello there! This article couldn’t be written any better!
    Looking through this article reminds me of my previous roommate!

    He continually kept preaching about this. I most
    certainly will send this article to him. Fairly certain he’s
    going to have a very good read. Thank you for sharing!

  44. Whats Taking place i am new to this, I stumbled upon this I have discovered It absolutely helpful and it has aided me out loads. I hope to contribute & aid other users like its aided me. Great job.

  45. This design is wicked! You certainly know how to keep a reader amused.
    Between your wit and your videos, I was almost
    moved to start my own blog (well, almost…HaHa!) Excellent
    job. I really loved what you had to say, and more than that, how
    you presented it. Too cool!

  46. Hello! I know this is somewhat off topic but I was wondering which blog platform are you using for this
    website? I’m getting fed up of WordPress because I’ve had issues with hackers and
    I’m looking at options for another platform. I would be great if you could point me
    in the direction of a good platform.

  47. It’s perfect time to make some plans for the longer term and
    it is time to be happy. I’ve learn this put up and if I could I desire to suggest you some
    attention-grabbing issues or suggestions. Maybe you can write subsequent articles relating to this article.
    I desire to learn more things approximately it!

  48. Its like you learn my mind! You appear to understand so much about this, like you wrote the book in it or something.
    I feel that you can do with a few % to power the message home a bit, but instead of
    that, that is magnificent blog. A great read.
    I’ll definitely be back.

  49. When I originally commented I seem to have clicked on the
    -Notify me when new comments are added- checkbox and now
    whenever a comment is added I receive 4 emails with the same comment.
    Perhaps there is a means you can remove me from that service?

    Thanks!

  50. I’d have to check with you here. Which isn’t something I normally do! I enjoy studying a post that will make folks think. Additionally, thanks for permitting me to remark!

发表评论

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