{"id":2023,"date":"2022-09-03T07:58:51","date_gmt":"2022-09-02T23:58:51","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=2023"},"modified":"2022-09-04T07:44:31","modified_gmt":"2022-09-03T23:44:31","slug":"noi-2022","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/noi-2022\/","title":{"rendered":"NOI 2022"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.zhihu.com\/question\/548696144\">https:\/\/www.zhihu.com\/question\/548696144<\/a><\/li>\n<li><a href=\"https:\/\/blog.csdn.net\/liuzhangfeiabc\/article\/details\/126594264\">https:\/\/blog.csdn.net\/liuzhangfeiabc\/article\/details\/126594264<\/a><\/li>\n<\/ul>\n<h2>D1T1<\/h2>\n<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P8496\">https:\/\/www.luogu.com.cn\/problem\/P8496<\/a><\/li>\n<\/ul>\n<p>\u4f1a\u7ef4\u62a4\u533a\u95f4\u7edd\u5bf9\u4f17\u6570\u7684\u8bdd\uff0c\u8fd9\u4e2a\u5c31\u662f\u9001\u5206\u9898\u4e86\u3002\u3002\u96be\u70b9\u81ea\u7136\u53ea\u5269\u4e0b\u5408\u5e76\u64cd\u4f5c\uff0c\u53ef\u4ee5\u9009\u62e9\u7684\u6709\u5e73\u8861\u6811\u542f\u53d1\u5f0f\u5408\u5e76\uff0c\u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811 \u6216 Treap\uff0c\u8fd9\u91cc\u8003\u8651\u7528\u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811\u3002<br \/>\n\u7136\u540e\u5355\u4e2a\u5e8f\u5217\u53ea\u6709\u5c3e\u90e8\u63d2\u5165\u548c\u5220\u9664\uff0c\u6240\u6709\u5c31\u662f\u6808\u7684\u94fe\u8868\uff0c\u7136\u540e\u6bcf\u4e2a\u94fe\u8868\u518d\u5bf9\u5e94\u4e00\u4e2a\u7ebf\u6bb5\u6811\u3002<br \/>\n\uff08\u4ec0\u4e48\uff0cvector \u5c45\u7136\u6bd4 stack \u8981\u5feb\uff1f\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\nconst int N = int(1e6) + 9, NN = 20*N;\r\nint n, q;\r\n\r\nstruct Chairman_Tree {\r\n#define lx c&#x5B;0]&#x5B;x]\r\n#define rx c&#x5B;1]&#x5B;x]\r\n#define ly c&#x5B;0]&#x5B;y]\r\n#define ry c&#x5B;1]&#x5B;y]\r\n#define ml ((l+r)&gt;&gt;1)\r\n#define mr (ml+1)\r\n#define lc lx, l, ml\r\n#define rc rx, mr, r\r\n    int c&#x5B;2]&#x5B;NN]; PII mx&#x5B;NN]; int tot;\r\n    int pp, dd;\r\n\r\n    int new_node() {\r\n        ++tot;\r\n        return tot;\r\n    }\r\n\r\n    void add(int&amp; x, int l = 1, int r = n + q) {\r\n        if (!x) x = new_node();\r\n        if (l == r) {\r\n            mx&#x5B;x].se = l;\r\n            mx&#x5B;x].fi += dd;\r\n        } else {\r\n            if (pp &lt; mr) add(lc); else add(rc);\r\n            mx&#x5B;x] = max(mx&#x5B;lx], mx&#x5B;rx]);\r\n        }\r\n    }\r\n\r\n    int query(int x, int l = 1, int r = n + q) {\r\n        if (l == r) return mx&#x5B;x].fi;\r\n        return pp &lt; mr ? query(lc) : query(rc);\r\n    }\r\n\r\n    void Add(int&amp; x, int p, int d) {\r\n        pp = p; dd = d; add(x);\r\n    }\r\n\r\n    int Query(int x, int p) {\r\n        pp = p;\r\n        return query(x);\r\n    }\r\n\r\n    int Merge(int x, int y) {\r\n        if (!x || !y) return x | y;\r\n        if (mx&#x5B;lx].se == mx&#x5B;rx].se) {\r\n            mx&#x5B;x].fi += mx&#x5B;y].fi;\r\n        } else {\r\n            lx = Merge(lx, ly);\r\n            rx = Merge(rx, ry);\r\n            mx&#x5B;x] = max(mx&#x5B;lx], mx&#x5B;rx]);\r\n        }\r\n        return x;\r\n    }\r\n} T;\r\n\r\nVI a&#x5B;N]; int l&#x5B;N],head&#x5B;N],tail&#x5B;N],sz&#x5B;N],rt&#x5B;N];\r\n\r\ninline void Add(int x, int y) {\r\n    a&#x5B;tail&#x5B;x]].PB(y);\r\n    T.Add(rt&#x5B;x], y, 1);\r\n    ++sz&#x5B;x];\r\n}\r\n\r\ninline void Del(int x) {\r\n    int &amp;t = tail&#x5B;x]; while(a&#x5B;t].empty()) t = l&#x5B;t];\r\n    T.Add(rt&#x5B;x],a&#x5B;t].back(),-1); a&#x5B;t].pop_back();\r\n    --sz&#x5B;x];\r\n}\r\n\r\ninline PII vote(int x) {\r\n    PII t = T.mx&#x5B;rt&#x5B;x]];\r\n    return {t.se, max(2*t.fi-sz&#x5B;x], sz&#x5B;x]&amp;1)};\r\n}\r\ninline PII operator +(PII x, PII y) {\r\n    if(x.fi == y.fi) return {x.fi, x.se + y.se};\r\n    if(x.se &gt; y.se) return {x.fi, x.se - y.se};\r\n    return {y.fi, y.se - x.se};\r\n}\r\ninline int Query() {\r\n    static int x&#x5B;N], m;\r\n    LL n = 0, c = 0; PII t = {0, 0};\r\n    RD(m); REP(i, m) {\r\n        n += sz&#x5B;RD(x&#x5B;i])];\r\n        t = t + vote(x&#x5B;i]);\r\n    }\r\n    REP(i, m) c += T.Query(rt&#x5B;x&#x5B;i]], t.fi);\r\n    return c * 2 &gt; n ? t.fi : -1;\r\n}\r\n\r\ninline void Merge(int x,int y,int z) {\r\n    head&#x5B;z] = head&#x5B;x]; tail&#x5B;z] = tail&#x5B;y]; l&#x5B;head&#x5B;y]] = tail&#x5B;x];\r\n    rt&#x5B;z] = T.Merge(rt&#x5B;x], rt&#x5B;y]); sz&#x5B;z] = sz&#x5B;x] + sz&#x5B;y];\r\n}\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    RD(n, q); REP_1(i, n) {\r\n        tail&#x5B;i] = head&#x5B;i] = i;\r\n        Rush Add(i,RD());\r\n    }\r\n\r\n    DO(q) {\r\n        int x,y,z,op; RD(op); if (op == 1) RD(x,y),Add(x,y);\r\n        else if (op == 2) Del(RD());\r\n        else if (op == 3) OT(Query());\r\n        else RD(x,y,z),Merge(x,y,z);\r\n    }\r\n}\r\n<\/pre>\n<h2>D1T2<\/h2>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/io&gt;\r\nusing namespace lastweapon;\r\n\r\n\r\nconst int N = int(1e3) + 5;\r\nint n, k, l&#x5B;N], r&#x5B;N];\r\nnamespace judge {\r\n  bool check() {\r\n    if(k) return 0;\r\n    for(int i = 1; i &lt;= n; i++) if(l&#x5B;i] != r&#x5B;i]) return 0;\r\n    return 1;\r\n  }\r\n  bool f&#x5B;N]&#x5B;3]&#x5B;3];\r\n  void solve() {\r\n    memset(f, 0, sizeof(f));\r\n    f&#x5B;1]&#x5B;0]&#x5B;0] = 1;\r\n    for(int i = 1; i &lt;= n; i++)\r\n      for(int j = 0; j &lt;= 2; j++)\r\n        for(int k = 0; k &lt;= 2; k++) {\r\n          if(!f&#x5B;i]&#x5B;j]&#x5B;k]) continue;\r\n          for(int st = 0; st &lt;= 2; st++) {\r\n            int val = l&#x5B;i] - j - k - st;\r\n            if(val &lt; 0 || val == 1) continue;\r\n            for(int nj = k; nj &lt;= min(2, j + k); nj++) f&#x5B;i + 1]&#x5B;nj]&#x5B;st] = 1;\r\n          }\r\n        }\r\n    cout &lt;&lt; f&#x5B;n + 1]&#x5B;0]&#x5B;0] &lt;&lt; &quot;\\n&quot;;\r\n  }\r\n}\r\nvoid solve() {\r\n  RD(n, k);\r\n  REP_1(i, n) RD(l&#x5B;i], r&#x5B;i]);\r\n  judge::solve();\r\n}\r\nint main() {\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    Rush solve();\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.zhihu.com\/question\/548696144 https:\/\/blog.csdn.net\/liuzhangfeiabc\/article\/details\/126594264 D1T1 https:\/\/www.luogu.com.cn\/problem\/P8496 \u4f1a\u7ef4\u62a4\u533a\u95f4\u7edd\u5bf9\u4f17\u6570\u7684\u8bdd\uff0c\u8fd9\u4e2a\u5c31\u662f\u9001\u5206\u9898\u4e86\u3002\u3002\u96be\u70b9\u81ea\u7136\u53ea\u5269\u4e0b\u5408\u5e76\u64cd\u4f5c\uff0c\u53ef\u4ee5\u9009\u62e9\u7684\u6709\u5e73\u8861\u6811\u542f\u53d1\u5f0f\u5408\u5e76\uff0c\u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811 \u6216 Treap\uff0c\u8fd9\u91cc\u8003\u8651\u7528\u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811\u3002 \u7136\u540e\u5355\u4e2a\u5e8f\u5217\u53ea\u6709\u5c3e\u90e8\u63d2\u5165\u548c\u5220\u9664\uff0c\u6240\u6709\u5c31\u662f\u6808\u7684\u94fe\u8868\uff0c\u7136\u540e\u6bcf\u4e2a\u94fe\u8868\u518d\u5bf9\u5e94\u4e00\u4e2a\u7ebf\u6bb5\u6811\u3002 \uff08\u4ec0\u4e48\uff0cvector \u5c45\u7136\u6bd4 stack \u8981\u5feb\uff1f\uff09 #include &lt;lastweapon\/io&gt; using namespace lastweapon; const int N = int(1e6) + 9, NN = 20*N; int n, q; struct Chairman_Tree { #define lx c&#x5B;0]&#x5B;x] #define rx c&#x5B;1]&#x5B;x] #define ly c&#x5B;0]&#x5B;y] #define ry c&#x5B;1]&#x5B;y] #define ml ((l+r)&gt;&gt;1) #define mr (ml+1) #define lc lx, l, [&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-2023","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-wD","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2023","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=2023"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2023\/revisions"}],"predecessor-version":[{"id":2025,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/2023\/revisions\/2025"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=2023"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=2023"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=2023"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}