{"id":2019,"date":"2022-09-03T03:24:49","date_gmt":"2022-09-02T19:24:49","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2019"},"modified":"2022-09-03T03:30:54","modified_gmt":"2022-09-02T19:30:54","slug":"luogu-3369","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-3369\/","title":{"rendered":"Luogu P3369 \u3010\u6a21\u677f\u3011\u666e\u901a\u5e73\u8861\u6811"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3369\">https:\/\/www.luogu.com.cn\/problem\/P3369<\/a><\/li>\n<\/ul>\n<pre class=\"brush: cpp; light: false; title: SBT; toolbar: true; notranslate\" title=\"SBT\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nnamespace SBT {\r\n    const static int N = int(1e5) + 9;\r\n    int c&#x5B;2]&#x5B;N], sz&#x5B;N], ky&#x5B;N], tot;\r\n#define l c&#x5B;d]\r\n#define r c&#x5B;!d]\r\n#define lx l&#x5B;x]\r\n#define rx r&#x5B;x]\r\n#define kx ky&#x5B;x]\r\n#define sx sz&#x5B;x]\r\n#define d 0\r\n    int new_node(int v = 0){\r\n        int x=tot++;lx=rx=0;\r\n        sx=1;kx=v;\r\n        return x;\r\n    }\r\n    void upd(int x){\r\n        sx=sz&#x5B;lx]+1+sz&#x5B;rx];\r\n    }\r\n#undef d\r\n    void rot(int &amp;x,int d){\r\n        int y=rx;rx=l&#x5B;y];l&#x5B;y]=x;\r\n        upd(x),upd(y),x=y;\r\n    }\r\n    void fix(int &amp;x,int d){\r\n        if (sz&#x5B;l&#x5B;lx]] &gt; sz&#x5B;rx]) rot(x,!d);\r\n        else{\r\n            if (sz&#x5B;r&#x5B;lx]] &gt; sz&#x5B;rx]) rot(lx,d),rot(x,!d);\r\n            else return;\r\n        }\r\n        d=0,fix(lx,0),fix(rx,1);\r\n        fix(x,0),fix(x,1);\r\n    }\r\n#define d 0\r\n    void Ins(int &amp;x,int v){\r\n        if(!x) x = new_node(v);\r\n        else{\r\n            ++sz&#x5B;x]; Ins(c&#x5B;v&gt;kx]&#x5B;x],v);\r\n            fix(x,v&gt;kx);\r\n        }\r\n    }\r\n    int d_key; void Del(int &amp;x,int v){\r\n        --sx;if(kx==v||(v&lt;kx&amp;&amp;!lx)||(v&gt;kx&amp;&amp;!rx)){\r\n            if(!lx||!rx) d_key = kx, x = lx | rx;\r\n            else Del(lx,v+1), kx = d_key;\r\n        }\r\n        else Del(c&#x5B;v&gt;kx]&#x5B;x],v);\r\n    }\r\n\r\n    int Rank(int x,int v) {\r\n        if (!x) return 0;\r\n        return v &lt;= kx ? Rank(lx, v) : sz&#x5B;lx] + 1 + Rank(rx, v);\r\n    }\r\n    int Select(int x,int k) {\r\n        if (k == sz&#x5B;lx]) return kx;\r\n        return k &lt; sz&#x5B;lx] ? Select(lx, k) : Select(rx, k-sz&#x5B;lx]-1);\r\n    }\r\n    int upper(int x, int k) {\r\n        int z;\r\n        while (x) {\r\n            if (kx &gt; k) z = x, x = lx;\r\n            else x = rx;\r\n        }\r\n        return ky&#x5B;z];\r\n    }\r\n    int lower(int x,int k) {\r\n        int z;\r\n        while (x) {\r\n            if (kx &lt; k) z = x, x = rx;\r\n            else x = lx;\r\n        }\r\n        return ky&#x5B;z];\r\n    }\r\n#undef d\r\n#undef sx\r\n#undef kx\r\n#undef lx\r\n#undef rx\r\n#undef l\r\n#undef r\r\n} using namespace SBT;\r\n\r\nint rt;\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    tot = 1;\r\n    int cmd, x;\r\n\r\n    Rush {\r\n        int cmd; RD(cmd); RD(x);\r\n        \/\/cout &lt;&lt; cmd &lt;&lt; &quot; &quot; &lt;&lt; x &lt;&lt; endl;\r\n        switch(cmd) {\r\n            case 1:\r\n                Ins(rt, x);\r\n                break;\r\n            case 2:\r\n                Del(rt, x);\r\n                break;\r\n            case 3:\r\n                OT(Rank(rt, x)+1);\r\n                break;\r\n            case 4:\r\n                OT(Select(rt, x-1));\r\n                break;\r\n            case 5:\r\n                \/\/OT(lower(rt, x));\r\n                OT(Select(rt, Rank(rt, x)-1));\r\n                break;\r\n            case 6:\r\n                \/\/OT(upper(rt, x));\r\n                OT(Select(rt, Rank(rt, x+1)));\r\n                break;\r\n        }\r\n    }\r\n}\r\n\r\n<\/pre>\n<pre class=\"brush: cpp; light: false; title: \u66ff\u7f6a\u7f8a\u6811; toolbar: true; notranslate\" title=\"\u66ff\u7f6a\u7f8a\u6811\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nnamespace Scapegoat_Tree {\r\n    const static int N = int(1e5) + 9;\r\n    const static DB alpha = 0.7;\r\n    int c&#x5B;2]&#x5B;N], sz&#x5B;N], ky&#x5B;N], tot;\r\n#define l c&#x5B;d]\r\n#define r c&#x5B;!d]\r\n#define lx l&#x5B;x]\r\n#define rx r&#x5B;x]\r\n#define kx ky&#x5B;x]\r\n#define sx sz&#x5B;x]\r\n#define d 0\r\n    int new_node(int v = 0){\r\n        int x=tot++;lx=rx=0;\r\n        sx=1;kx=v;\r\n        return x;\r\n    }\r\n    void upd(int x){\r\n        sx=sz&#x5B;lx]+1+sz&#x5B;rx];\r\n    }\r\n    bool bad(int x) {\r\n        return max(sz&#x5B;lx], sz&#x5B;rx]) &gt;= int(sx * alpha);\r\n    }\r\n    void build(int &amp;x, int ll, int rr, VI&amp; T) {\r\n        if (ll &gt;= rr) x = 0;\r\n        else {\r\n            int ml = (ll+rr) &gt;&gt; 1, mr = ml + 1;\r\n            x = T&#x5B;ml];\r\n            build(lx, ll, ml, T);\r\n            build(rx, mr, rr, T);\r\n            upd(x);\r\n        }\r\n    }\r\n    void collect(int x, VI&amp; T) {\r\n        if (!x) return;\r\n        collect(lx, T); T.PB(x); collect(rx, T);\r\n    }\r\n    void rebuild(int&amp; x) {\r\n        VI T; collect(x, T);\r\n        build(x, 0, SZ(T), T);\r\n    }\r\n    void Ins(int &amp;x,int v){\r\n        if(!x) x = new_node(v);\r\n        else{\r\n            ++sz&#x5B;x]; Ins(c&#x5B;v&gt;kx]&#x5B;x],v);\r\n            if (bad(x)) rebuild(x);\r\n        }\r\n    }\r\n    int d_key; void Del(int &amp;x,int v){\r\n        --sx;if(kx==v||(v&lt;kx&amp;&amp;!lx)||(v&gt;kx&amp;&amp;!rx)){\r\n            if(!lx||!rx) d_key = kx, x = lx | rx;\r\n            else Del(lx,v+1), kx = d_key;\r\n        }\r\n        else Del(c&#x5B;v&gt;kx]&#x5B;x],v);\r\n    }\r\n\r\n    int Rank(int x,int v) {\r\n        if (!x) return 0;\r\n        return v &lt;= kx ? Rank(lx, v) : sz&#x5B;lx] + 1 + Rank(rx, v);\r\n    }\r\n    int Select(int x,int k) {\r\n        if (k == sz&#x5B;lx]) return kx;\r\n        return k &lt; sz&#x5B;lx] ? Select(lx, k) : Select(rx, k-sz&#x5B;lx]-1);\r\n    }\r\n    int upper(int x, int k) {\r\n        int z;\r\n        while (x) {\r\n            if (kx &gt; k) z = x, x = lx;\r\n            else x = rx;\r\n        }\r\n        return ky&#x5B;z];\r\n    }\r\n    int lower(int x,int k) {\r\n        int z;\r\n        while (x) {\r\n            if (kx &lt; k) z = x, x = rx;\r\n            else x = lx;\r\n        }\r\n        return ky&#x5B;z];\r\n    }\r\n\r\n    void inorder(int x) {\r\n        if (!x) return;\r\n        inorder(lx);\r\n        printf(&quot;%d &quot;, ky&#x5B;x]);\r\n        inorder(rx);\r\n    }\r\n\r\n#undef d\r\n#undef sx\r\n#undef kx\r\n#undef lx\r\n#undef rx\r\n#undef l\r\n#undef r\r\n} using namespace Scapegoat_Tree;\r\n\r\nint rt;\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    tot = 1;\r\n    int cmd, x;\r\n\r\n    Rush {\r\n        int cmd; RD(cmd); RD(x);\r\n        switch(cmd) {\r\n            case 1:\r\n                Ins(rt, x);\r\n                break;\r\n            case 2:\r\n                Del(rt, x);\r\n                break;\r\n            case 3:\r\n                OT(Rank(rt, x)+1);\r\n                break;\r\n            case 4:\r\n                OT(Select(rt, x-1));\r\n                break;\r\n            case 5:\r\n                OT(lower(rt, x));\r\n                \/\/OT(Select(rt, Rank(rt, x)-1));\r\n                break;\r\n            case 6:\r\n                OT(upper(rt, x));\r\n                \/\/OT(Select(rt, Rank(rt, x+1)));\r\n                break;\r\n        }\r\n    }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P3369 #include &lt;lastweapon\/io&gt; using namespace lastweapon; namespace SBT { const static int N = int(1e5) + 9; int c&#x5B;2]&#x5B;N], sz&#x5B;N], ky&#x5B;N], tot; #define l c&#x5B;d] #define r c&#x5B;!d] #define lx l&#x5B;x] #define rx r&#x5B;x] #define kx ky&#x5B;x] #define sx sz&#x5B;x] #define d 0 int new_node(int v = 0){ int x=tot++;lx=rx=0; sx=1;kx=v; return x; } void [&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-2019","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wz","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2019","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=2019"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2019\/revisions"}],"predecessor-version":[{"id":2020,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2019\/revisions\/2020"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2019"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2019"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2019"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}