{"id":2002,"date":"2022-07-29T21:06:20","date_gmt":"2022-07-29T13:06:20","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2002"},"modified":"2022-07-29T21:06:46","modified_gmt":"2022-07-29T13:06:46","slug":"jsoi2008blue-mary%e5%bc%80%e5%85%ac%e5%8f%b8","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/jsoi2008blue-mary%e5%bc%80%e5%85%ac%e5%8f%b8\/","title":{"rendered":"[JSOI2008]Blue Mary\u5f00\u516c\u53f8"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4254\">https:\/\/www.luogu.com.cn\/problem\/P4254<\/a><\/li>\n<li><a href=\"https:\/\/darkbzoj.cc\/problem\/1568\">https:\/\/darkbzoj.cc\/problem\/1568<\/a><\/li>\n<\/ul>\n<p><a href=\"https:\/\/github.com\/kth-competitive-programming\/kactl\/blob\/main\/content\/data-structures\/LineContainer.h\">\u8fd9\u4e2a<\/a> \u53ef\u771f\u68d2\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#define ll double\r\nstruct Line {\r\n\tmutable ll k, b, p;\r\n\tLine (ll k = 0, ll b = 0):k(k),b(b){\r\n\t    p = 0;\r\n\t}\r\n\tll y(ll x) const {return k*x + b;}\r\n\tbool operator&lt;(const Line&amp; o) const { return k &lt; o.k; }\r\n\tbool operator&lt;(ll x) const { return p &lt; x; }\r\n};\r\n\r\nstruct LineContainer : multiset&lt;Line,less&lt;&gt;&gt; {\r\n\tconst ll inf = 1\/.0;\r\n\tll div(ll a, ll b) {\r\n\t\treturn a \/ b;\r\n    }\r\n\tbool isect(iterator x, iterator y) {\r\n\t\tif (y == end()) return x-&gt;p = inf, 0;\r\n\t\tif (x-&gt;k == y-&gt;k) x-&gt;p = x-&gt;b &gt; y-&gt;b ? inf : -inf;\r\n\t\telse x-&gt;p = div(y-&gt;b - x-&gt;b, x-&gt;k - y-&gt;k);\r\n\t\treturn x-&gt;p &gt;= y-&gt;p;\r\n\t}\r\n\tvoid add(ll k, ll b) {\r\n\t\tadd(Line(k,b));\r\n\t}\r\n\tvoid add(Line t) {\r\n\t\tauto z = insert(t), y = z++, x = y;\r\n\t\twhile (isect(y, z)) z = erase(z);\r\n\t\tif (x != begin() &amp;&amp; isect(--x, y)) isect(x, y = erase(y));\r\n\t\twhile ((y = x) != begin() &amp;&amp; (--x)-&gt;p &gt;= y-&gt;p)\r\n\t\t\tisect(x, erase(y));\r\n\t}\r\n\r\n\tll query(ll x) {\r\n\t\tassert(!empty());\r\n\t\tauto&amp; l = *lower_bound(x);\r\n\t\treturn l.y(x);\r\n\t}\r\n} H;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/ freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    H.add(0, 0); char cmd&#x5B;10]; DB k, b, x; Rush {\r\n        RS(cmd);\r\n        if (cmd&#x5B;0] == 'P') {\r\n            RF(b, k);\r\n            H.add(k, b);\r\n        } else {\r\n            RF(x);\r\n            OT(LL(H.query(x-1)\/100));\r\n        }\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P4254 https:\/\/darkbzoj.cc\/problem\/1568 \u8fd9\u4e2a \u53ef\u771f\u68d2\u3002\u3002\u3002 #define ll double struct Line { mutable ll k, b, p; Line (ll k = 0, ll b = 0):k(k),b(b){ p = 0; } ll y(ll x) const {return k*x + b;} bool operator&lt;(const Line&amp; o) const { return k &lt; o.k; } bool operator&lt;(ll x) const { return p &lt; [&hellip;]<\/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":[1],"tags":[],"class_list":["post-2002","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wi","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2002","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=2002"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2002\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2002"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2002"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}