{"id":758,"date":"2013-06-27T00:52:52","date_gmt":"2013-06-26T16:52:52","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=758"},"modified":"2015-07-05T04:21:07","modified_gmt":"2015-07-04T20:21:07","slug":"hdu-3308-lcis","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/hdu-3308-lcis\/","title":{"rendered":"HDU 3308. LCIS"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>&#8230; \u52a8\u6001\u7ef4\u62a4\u4e00\u4e2a\u6570\u7ec4 A[]\uff0c\u652f\u6301\u4ee5\u4e0b\u4e24\u79cd\u64cd\u4f5c<\/p>\n<ul>\n<li><code>U a b<\/code>: \u5355\u70b9\u4fee\u6539\uff0c\u5c06 A[a] \u66ff\u6362\u6210 b\u3002(\u4ece 0 \u6807\u53f7\u3002\u3002)<\/li>\n<li><code>Q a b<\/code>: \u533a\u95f4\u8be2\u95ee\uff0c\u8be2\u95ee [a, b] \u533a\u95f4\u7684 LCIS (Longest Continuous Increase Subsequence, \u6700\u957f\u8fde\u7eed\u9012\u589e\u5b50\u5e8f\u5217) \u7684\u957f\u5ea6\u3002<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h3>Analysis: <\/h3>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nstruct Seg{\r\n    int ll, rr, ss;\r\n} T&#x5B;4*N];\r\n\r\n...\r\n\r\nvoid Update(int x, int l, int r){\r\n    T&#x5B;x].ll = T&#x5B;lx].ll, T&#x5B;x].rr = T&#x5B;rx].rr;\r\n    T&#x5B;x].ss = max(T&#x5B;lx].ss, T&#x5B;rx].ss);\r\n    if (A&#x5B;ml] &lt; A&#x5B;mr]){\r\n        if (T&#x5B;x].ll == mr - l) T&#x5B;x].ll += T&#x5B;rx].ll;\r\n        if (T&#x5B;x].rr == r - ml) T&#x5B;x].rr += T&#x5B;lx].rr;\r\n        checkMax(T&#x5B;x].ss, T&#x5B;lx].rr + T&#x5B;rx].ll);\r\n    }\r\n}\r\n<\/pre>\n<p><a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/contest\/viewSource.action?id=3946299\">http:\/\/acm.hust.edu.cn\/vjudge\/contest\/viewSource.action?id=3946299<\/a><\/p>\n<h3>External link: <\/h3>\n<p>&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: &#8230; \u52a8\u6001\u7ef4\u62a4\u4e00\u4e2a\u6570\u7ec4 A[]\uff0c\u652f\u6301\u4ee5\u4e0b\u4e24\u79cd\u64cd\u4f5c U a b: \u5355\u70b9\u4fee\u6539\uff0c\u5c06 A[a] \u66ff\u6362\u6210 b\u3002(\u4ece 0 \u6807\u53f7\u3002\u3002) Q a b: \u533a\u95f4\u8be2\u95ee\uff0c\u8be2\u95ee [a, b] \u533a\u95f4\u7684 LCIS (Longest Continuous Increase Subsequence, \u6700\u957f\u8fde\u7eed\u9012\u589e\u5b50\u5e8f\u5217) \u7684\u957f\u5ea6\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[16],"tags":[],"class_list":["post-758","post","type-post","status-publish","format-standard","hentry","category-online-judge"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-ce","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/758","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=758"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/758\/revisions"}],"predecessor-version":[{"id":1148,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/758\/revisions\/1148"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=758"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}