{"id":597,"date":"2012-12-17T06:35:03","date_gmt":"2012-12-16T22:35:03","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=597"},"modified":"2021-09-11T04:25:31","modified_gmt":"2021-09-10T20:25:31","slug":"luogu-p4198-%e6%a5%bc%e6%88%bf%e9%87%8d%e5%bb%ba","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p4198-%e6%a5%bc%e6%88%bf%e9%87%8d%e5%bb%ba\/","title":{"rendered":"Luogu P4198. \u697c\u623f\u91cd\u5efa"},"content":{"rendered":"

Brief description: <\/h3>\n

\u3002\u3002\u7ef4\u62a4\u4e00\u4e2a\u533a\u95f4\u3002\u3002\u6bcf\u4e2a\u4f4d\u7f6e\u6709\u4e00\u4e2a\u697c\u623f\u3002\u3002\u3002\u95ee\u4e00\u4e2a\u4eba\u7ad9\u5728 (0, 0) \u4f4d\u7f6e\u3002\u3002\u62ac\u5934\u6700\u591a\u80fd\u770b\u5230\u591a\u5c11\u697c\u623f\u3002\u3002
\n\u3002\u3002\uff08\u3002\u652f\u6301\u5355\u70b9\u4fee\u6539\u3002<\/p>\n

Analysis: <\/h3>\n

\u524d\u7565\uff0c\u586b\u8fc7\u7684\u6e05\u6a59 OJ\u3002
\n\u5982\u4f55\u80fd O(1) \u65f6\u7a7a \u7684\u5224\u65ad\u4e00\u4e2a\u8282\u70b9\u662f\u5426\u662f\u53f6\u5b50\u8282\u70b9\uff1f<\/p>\n

\r\nconst int N = int(1e5) + 9;\r\n\r\nnamespace Segment_Tree {\r\n#define lx (x<<1)\r\n#define rx (lx|1)\r\n#define ml (l+r>>1)\r\n#define mr (ml+1)\r\n#define lc lx, l, ml\r\n#define rc rx, mr, r\r\n#define root 1, 1, n\r\n    const int NN = 4*N;\r\n    DB mx[NN]; int jp[NN];\r\n    int a, b, n;\r\n\r\n    int Jmp(int x, int l, int r, DB h){\r\n        if (l < r) return mx[lx] < h ? Jmp(rc, h) : jp[x] - jp[lx] + Jmp(lc, h);\r\n        return h < mx[x];\r\n    }\r\n\r\n    void upd(int x, int l, int r){\r\n        mx[x] = max(mx[lx], mx[rx]);\r\n        jp[x] = jp[lx] + Jmp(rc, mx[lx]);\r\n    }\r\n\r\n    void Modify(int x, int l, int r) {\r\n        if (l == r) {\r\n            mx[x] = (DB) b \/ a;\r\n            jp[x] = 1;\r\n        } else {\r\n            if (a < mr) Modify(lc);\r\n            else Modify(rc);\r\n            upd(x,l,r);\r\n        }\r\n    }\r\n} using namespace Segment_Tree;\r\n\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n    RD(n); Rush {\r\n        RD(a, b); Modify(root);\r\n        OT(jp[1]);\r\n    }\r\n}\r\n<\/pre>\n
\u2014\u2014\u2014\u2014 UPD 2021\/09\/10 \u2014\u2014\u2014\u2014<\/p>\n
\uff08\u3002\u8fd9\u4e2a\u9898\u7ebf\u6bb5\u6811\u7684\u505a\u6cd5\u6709\u70b9\u5389\u5bb3\u3002\u3002\u3002\u4ee5\u4e0b\u76f4\u63a5\u8d34 Seter \u9898\u89e3\u3002\u3002\u3002<\/p>\n
<\/p>\n
\n\u534a\u5e74\u524d\u548c\u4e3b\u5e2d\u8ba8\u8bba\u8fc7\u7c7b\u4f3c\u7684\u95ee\u9898\uff0c\u5f97\u51fa\u7684\u7ed3\u8bba\u662f\u53ea\u80fdsqrtnlgn\uff0c\u518d\u600e\u4e48\u4f18\u5316\u4e5f\u53ea\u80fdsqrtn\u3002\u3002
\n\u7ed3\u679c\u5c45\u7136\u6709\u7ebf\u6bb5\u6811\u505a\u6cd5\u3002\u3002
\n\u9996\u5148\u6211\u4eec\u628a\u6bcf\u4e2a\u623f\u5c4b\u7684Y\u9664\u4ee5X\uff0c\u518d\u5728\u6700\u5de6\u8fb9\u52a0\u4e2a0\uff0c\u8fd9\u6837\u7684\u8bdd\uff0c\u7b54\u6848\u5c31\u662f\u4ece0\u5f00\u59cb\uff0c\u6bcf\u6b21\u5f80\u53f3\u8fb9\u8df3\u5230\u4e25\u683c\u6bd4\u5b83\u5927\u7684\u7b2c\u4e00\u4e2a\u6570\u4e0a\uff0c\u76f4\u5230\u4e0d\u80fd\u8df3\u4e3a\u6b62\uff0c\u603b\u5171\u8df3\u4e86\u51e0\u6b21\u3002\u3002
\n\u6bd4\u5982\u5f97\u51fa\u6765\u662f0 2 1.5 2.333\uff0c\u90a3\u5c31\u662f\u8df3\u4e862\u6b21\uff0c\u7b54\u6848\u5c31\u662f2\u3002
\n\u5f53\u65f6\u53ea\u60f3\u51fa\u4e86\u5206\u5757\u3002\u3002\u95ee\u4e86\u4e00\u4e9b\u795e\u7287\u4ed6\u4eec\u90fd\u4e0d\u80af\u597d\u597d\u5e2e\u5fd9\u60f3\u3002\u3002\u4e8e\u662f\u5c31\u6401\u7f6e\u4e86\u3002\u3002
\n\u6807\u7a0b\u662f\u4e00\u79cd\u7ebf\u6bb5\u6811\u505a\u6cd5\u3002\u3002
\n\u9996\u5148\u6ce8\u610f\u5230\uff0c\u5728\u4e00\u6bb5\u4e2d\u8df3\uff0c\u6700\u540e\u5fc5\u5b9a\u5728\u6700\u5927\u7684\u90a3\u4e2a\u6570\u4e0a\u505c\u4e0b\u6765\u3002
\n\u6bcf\u4e2a\u70b9\u4ee3\u8868\u4e00\u4e2a\u533a\u95f4\uff0c\u7ef4\u62a4\u4e24\u4e2a\u4e1c\u897f\uff1a\u8fd9\u4e2a\u533a\u95f4\u7684\u6700\u5927\u6570\u548c\u8fd9\u4e2a\u533a\u95f4\u7684\u6700\u5de6\u8fb9\u52a0\u4e2a0\u540e\u4ece0\u5f00\u59cb\u5f80\u53f3\u8df3\u80fd\u8df3\u51e0\u6b21\u3002\n<\/p><\/blockquote>\n
\r\nconst int _N = 100009, N = _N * 4;\r\nint lc[N], rc[N]; DB mm[N]; int jp[N]; \/\/ \u8fd9\u4e2a\u533a\u95f4\u7684\u6700\u5927\u6570\u548c\u8fd9\u4e2a\u533a\u95f4\u7684\u6700\u5de6\u8fb9\u52a0\u4e2a 0 \u540e\u4ece 0 \u5f00\u59cb\u5f80\u53f3\u8df3\u80fd\u8df3\u51e0\u6b21\u3002 \r\nint nn; int xx, yy; DB slop;\r\nint n, root;\r\n.. .\r\n<\/pre>\n
\n\u7136\u540e\u6bcf\u4e2a\u8282\u70b9\u518d\u652f\u6301\u4e00\u4e2a\u64cd\u4f5c\uff1a\u5047\u8bbe\u6700\u5de6\u8fb9\u6765\u4e86\u4e2ax\uff0c\u5728\u8fd9\u4e2a\u533a\u95f4\u4e2d\uff0c\u4ece x \u5f00\u59cb\u5f80\u53f3\u8df3\u80fd\u8df3\u51e0\u6b21\u3002
\n\u8fd9\u4e2a\u64cd\u4f5c\u6709\u54ea\u4e9b\u7528\u5904\u5462\uff1f
\n\u7b2c\u4e00\u5c31\u662fx=0\u65f6\uff0c\u5f97\u51fa\u7684\u7b54\u6848\u6070\u597d\u5c31\u662f\u8fd9\u4e2a\u70b9\u4e2d\u8981\u7ef4\u62a4\u7684\u90a3\u4e2a\u4e1c\u897f\u3002
\n\u7b2c\u4e8c\u5c31\u662f\uff0c\u6211\u53ef\u4ee5\u5408\u5e76\u4e24\u4e2a\u76f8\u90bb\u533a\u95f4\u7684\u4ece0\u5f00\u59cb\u8df3\u7684\u7b54\u6848\u4e86\uff01\u56e0\u4e3a\u6211\u5fc5\u5b9a\u662f\u4ece0\u5f00\u59cb\u8df3\u5230\u5de6\u513f\u5b50\u7684\u6700\u5927\u6570\u4e0a\uff0c\u7136\u540e\u518d\u4ece\u5de6\u513f\u5b50\u7684\u6700\u5927\u6570\u5f00\u59cb\u5f80\u53f3\u513f\u5b50\u8df3\u3002\n<\/p><\/blockquote>\n
\r\nvoid Upd(int x){\r\n    mm[x] = max(mm[lx], mm[rx]);\r\n    jp[x] = jp[lx] + Jmp(rx, mm[lx]);\r\n}\r\n.. .\r\n<\/pre>\n
\n\u5219\u6574\u4e2a\u533a\u95f4\u7684\u7b54\u6848\u5c31\u662f\uff0c\u5de6\u513f\u5b50\u4ece0\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff08\u8fd9\u4e2a\u76f4\u63a5\u7ef4\u62a4\u4e86\uff09\uff0c\u52a0\u4e0a\u53f3\u513f\u5b50\u4ece\u5de6\u513f\u5b50\u6700\u5927\u6570\uff08\u8fd9\u4e2a\u4e5f\u76f4\u63a5\u7ef4\u62a4\u4e86\uff09\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff08\u8fd9\u4e2a\u9012\u5f52\u4e0b\u53bb\u7b97\uff09\u3002
\n\u7531\u4e8e\u6bcf\u6b21\u53ea\u9012\u5f52\u53f3\u513f\u5b50\uff0c\u6240\u4ee5\u6bcf\u4e2a\u70b9\u7b97\u7b54\u6848\u8fd8\u662flgn\u7684\uff0c\u8fd9\u6837\u5c31\u53ef\u4ee5lg^2n\u4fee\u6539\u4e86\u3002
\n—————————————————————————————————————————–
\n\u90a3\u600e\u4e48\u624d\u80fd\u5b9e\u73b0\u8fd9\u4e2a\u64cd\u4f5c\u5462\uff1f
\n\u6211\u4eec\u53d1\u73b0\uff0c\u5982\u679cx\u6bd4\u5de6\u513f\u5b50\u7684\u6700\u5927\u6570\u8fd8\u8981\u5927\uff0c\u90a3\u4e48\u5de6\u513f\u5b50\u5c31\u662f\u6ca1\u6709\u7528\u7684\uff0c\u76f4\u63a5\u8fd4\u56de\u53f3\u513f\u5b50\u7684\u7b54\u6848\u5c31\u53ef\u4ee5\u4e86\u3002
\n\u5426\u5219\u5462\uff1f\u96be\u9053\u8981\u8fd4\u56de\u5de6\u513f\u5b50\u4ecex\u5f00\u59cb\u8df3\u7684\u7b54\u6848\u52a0\u4e0a\u53f3\u513f\u5b50\u4ece\u5de6\u513f\u5b50\u6700\u5927\u6570\u5f00\u59cb\u8df3\u7684\u7b54\u6848\u5417\uff1f\u53ef\u662f\u8fd9\u6837\u4e24\u8fb9\u90fd\u8981\u9012\u5f52\u4e86\uff0c\u590d\u6742\u5ea6\u5c31\u574f\u6389\u4e86\u3002\u3002
\n\u6211\u4eec\u518d\u6765\u770b\u770b\u4e0a\u9762\u63d0\u5230\u7684\u5408\u5e76\u533a\u95f4\u7684\u65b9\u6cd5\uff1a
\n\u201c\u5219\u6574\u4e2a\u533a\u95f4\u7684\u7b54\u6848\u5c31\u662f\uff0c\u5de6\u513f\u5b50\u4ece0\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff08\u8fd9\u4e2a\u76f4\u63a5\u7ef4\u62a4\u4e86\uff09\uff0c\u52a0\u4e0a\u53f3\u513f\u5b50\u4ece\u5de6\u513f\u5b50\u6700\u5927\u6570\uff08\u8fd9\u4e2a\u4e5f\u76f4\u63a5\u7ef4\u62a4\u4e86\uff09\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff08\u8fd9\u4e2a\u9012\u5f52\u4e0b\u53bb\u7b97\uff09\u3002\u201d
\n\u6362\u53e5\u8bdd\u8bf4\uff0c\u53f3\u513f\u5b50\u4ece\u5de6\u513f\u5b50\u6700\u5927\u6570\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff0c\u5c31\u662f\u6574\u4e2a\u533a\u95f4\u4ece0\u5f00\u59cb\u8df3\u7684\u7b54\u6848\u51cf\u53bb\u5de6\u513f\u5b50\u4ece0\u5f00\u59cb\u8df3\u7684\u7b54\u6848\uff0c\u800c\u8fd9\u4e24\u4e2a\u7b54\u6848\u90fd\u76f4\u63a5\u7ef4\u62a4\u4e86\uff01
\n\u6240\u4ee5\u8fd9\u4e5f\u53ea\u9700\u8981\u9012\u5f52\u4e00\u4e2a\u513f\u5b50\u5373\u53ef\u3002\n<\/p><\/blockquote>\n
\r\nint Jmp(int x, DB h){\r\n    if (lx) return mm[lx] <= h ? Jmp(rx, h) : jp[x] - jp[lx] + Jmp(lx, h);\r\n    return h < mm[x];\r\n}\r\n.. .\r\n<\/pre>\n
\n\u6574\u4f53\u590d\u6742\u5ea6\u662flg^2n\u7684\u3002\n<\/p><\/blockquote>\n
\u9ad8\u7aef\u7ebf\u6bb5\u6811<\/a>
\n\u3002\u9ad8\u7aef\u7ebf\u6bb5\u6811\u3002\uff08\u5806\u5f0f\u5b58\u50a8\u3002\u3002<\/a><\/p>\n
External link: <\/h3>\n
https:\/\/www.luogu.com.cn\/problem\/P4198<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: \u3002\u3002\u7ef4\u62a4\u4e00\u4e2a\u533a\u95f4\u3002\u3002\u6bcf\u4e2a\u4f4d\u7f6e\u6709\u4e00\u4e2a\u697c\u623f\u3002\u3002\u3002\u95ee\u4e00\u4e2a\u4eba\u7ad9\u5728 (0, 0) \u4f4d\u7f6e\u3002\u3002\u62ac\u5934\u6700\u591a\u80fd\u770b\u5230\u591a\u5c11\u697c\u623f\u3002\u3002 \u3002\u3002\uff08\u3002\u652f\u6301\u5355\u70b9\u4fee\u6539\u3002 Analysis: \u524d\u7565\uff0c\u586b\u8fc7\u7684\u6e05\u6a59 OJ\u3002 \u5982\u4f55\u80fd O(1) \u65f6\u7a7a \u7684\u5224\u65ad\u4e00\u4e2a\u8282\u70b9\u662f\u5426\u662f\u53f6\u5b50\u8282\u70b9\uff1f const int N = int(1e5) + 9; namespace Segment_Tree { #define lx (x<<1) #define rx (lx|1) #define ml (l+r>>1) #define mr (ml+1) #define lc lx, l, ml #define rc rx, mr, r #define root 1, 1, n const int NN = […]<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[99],"class_list":["post-597","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-99"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-9D","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/597","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=597"}],"version-history":[{"count":2,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/597\/revisions"}],"predecessor-version":[{"id":1764,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/597\/revisions\/1764"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=597"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=597"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=597"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}