{"id":1992,"date":"2022-07-15T16:40:01","date_gmt":"2022-07-15T08:40:01","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=1992"},"modified":"2022-07-15T22:25:33","modified_gmt":"2022-07-15T14:25:33","slug":"bzoj-3681-arietta","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-3681-arietta\/","title":{"rendered":"BZOJ #3681. Arietta"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/darkbzoj.cc\/problem\/3681\">https:\/\/darkbzoj.cc\/problem\/3681<\/a><\/li>\n<\/ul>\n<p>\u7f51\u7edc\u6d41\u5efa\u6a21\u4e0a\u6bd4\u4e0a\u9898\u8981\u7b80\u5355\u3002<br \/>\n\u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811\u65b9\u9762\u9700\u8981\u7ebf\u6bb5\u6811\u5408\u5e76\u3002<br \/>\n\u603b\u4e4b\u8fd8\u662f\u6bd4\u4e0a\u4e00\u9898\u7b80\u5355\u3002<\/p>\n<p>darkbzoj \u4e0d\u652f\u6301 cpp14\uff0c\u65e0\u6cd5\u65b9\u4fbf\u7684\u4f7f\u7528 atl\u3002\u3002\u3002\uff08\u81f3\u5c11\u6211\u4e0d\u77e5\u9053\u600e\u4e48\u6539\u3002\u3002\u3002\uff09<br \/>\n\u503c\u5f97\u6ce8\u610f\u7684\u662f\u5bf9\u6743\u503c\u91cd\u590d\u8282\u70b9\u7684\u5904\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u5728\u53f6\u5b50\u4f4d\u7f6e\u52a8\u6001\u521b\u5efa\u65b0\u7684\u8282\u70b9\uff0c<br \/>\n\u628a\u65e7\u53f6\u5b50\u90fd\u5305\u542b\u5728\u5185\uff0c\u4e0d\u5f71\u54cd\u590d\u6742\u5ea6\u3002<\/p>\n<p>\u53e6\u5916\u5bf9\u4e8e\u4e4b\u524d\u7684\u8fd9\u7c7b\u6811\u4e0a\u7ebf\u6bb5\u6811\u5408\u5e76\u95ee\u9898\uff0cmerge \u7684\u65f6\u5019\u6211\u4eec\u53ef\u4ee5\u7834\u574f\u6389\u4e4b\u524d\u7684\u72b6\u6001\uff0c\u8986\u76d6\u5f0f\u66f4\u65b0\u800c\u4e0d\u53bb <code>new_node()<\/code> \u4ee5\u51cf\u5c11\u5185\u5b58\u5f00\u652f\u3002<br \/>\n\u4f46\u662f\u8fd9\u4e2a\u9898\u91cc\u6211\u4eec\u5fc5\u987b\u533a\u522b\u51fa\u8fd9\u4e9b\u72b6\u6001\uff08\u5efa\u56fe\u7684\u65f6\u5019\u4f1a query \u5230\uff09\uff0c\u6240\u4ee5\u8fd8\u662f\u8001\u5b9e\u7684\u6bcf\u6b21\u90fd <code>new_node()<\/code> \u4e3a\u597d\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\nconst int N = int(1e4) + 9;\r\n\r\nstruct Network_Flow{\r\nconst static int N = int(1e6) + 6, M = 2*N;\r\nint D&#x5B;N], hd&#x5B;N], suc&#x5B;M], to&#x5B;M], cap&#x5B;M];\r\nint n, m, s, t;\r\n\r\ninline void add_edge(int x, int y, int c){\r\n    suc&#x5B;m] = hd&#x5B;x], hd&#x5B;x] = m, to&#x5B;m] = y, cap&#x5B;m++] = c,\r\n    suc&#x5B;m] = hd&#x5B;y], hd&#x5B;y] = m, to&#x5B;m] = x, cap&#x5B;m++] = 0;\r\n}\r\n\r\ninline void add_edgee(int x, int y, int c){\r\n    suc&#x5B;m] = hd&#x5B;x], hd&#x5B;x] = m, to&#x5B;m] = y, cap&#x5B;m++] = c,\r\n    suc&#x5B;m] = hd&#x5B;y], hd&#x5B;y] = m, to&#x5B;m] = x, cap&#x5B;m++] = c;\r\n}\r\n\r\n#define v to&#x5B;i]\r\n#define c cap&#x5B;i]\r\n#define f cap&#x5B;i^1]\r\n\r\nbool bfs(){\r\n    static int Q&#x5B;N]; int cz = 0, op = 1;\r\n    fill(D, D+n, 0), D&#x5B;Q&#x5B;0] = s] = 1; while (cz &lt; op){\r\n        int u = Q&#x5B;cz++]; REP_G(i, u) if (!D&#x5B;v]&amp;&amp;c){\r\n            D&#x5B;Q&#x5B;op++]=v] = D&#x5B;u]+1;\r\n            if (v==t) return 1;\r\n        }\r\n    }\r\n    return 0;\r\n}\r\n\r\nLL Dinitz(){\r\n    LL z=0; while (bfs()){\r\n        static int cur&#x5B;N], pre&#x5B;N];\r\n        int u=s;pre&#x5B;s]=-1;cur&#x5B;s]=hd&#x5B;s];while (~u){\r\n#define i cur&#x5B;u]\r\n            if (u==t){\r\n                int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);\r\n                z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;\r\n            }\r\n#undef i\r\n            int i;for(i=cur&#x5B;u];i;i=suc&#x5B;i])if(D&#x5B;u]+1==D&#x5B;v]&amp;&amp;c){cur&#x5B;u]=i,cur&#x5B;v]=hd&#x5B;v],pre&#x5B;v]=u,u=v;break;}\r\n            if (!i)D&#x5B;u]=0,u=pre&#x5B;u];\r\n        }\r\n    }\r\n    return z;\r\n}\r\n#undef f\r\n#undef c\r\n#undef v\r\n} G;\r\n\r\n\r\n\r\nint T&#x5B;N], H&#x5B;N]; VI adj&#x5B;N];\r\nint n, m;\r\n\r\nnamespace 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    const int NN = 100*N;\r\n    int c&#x5B;2]&#x5B;NN]; int tot;\r\n    int pp;\r\n    int new_node() {\r\n        return ++tot;\r\n    }\r\n    int new_node(int y) {\r\n        int x = ++tot; lx = ly; rx = ry;\r\n        return x;\r\n    }\r\n\r\n    void Init(int &amp;x, int l = 1, int r = n) {\r\n        x = new_node();\r\n        if (l == r) {\r\n            G.add_edge(x, G.t, 1);\r\n        } else {\r\n            if (pp &lt; mr) Init(lc);\r\n            else Init(rc);\r\n        }\r\n    }\r\n\r\n    int Merge(int x, int y, int l = 1, int r = n) {\r\n        if (!x || !y) return x | y;\r\n        if (l == r) {\r\n            int z = new_node();\r\n            c&#x5B;0]&#x5B;z] = x;\r\n            c&#x5B;1]&#x5B;z] = y;\r\n            return z;\r\n        }\r\n        x = new_node(x);\r\n        lx = Merge(lx, ly, l, ml);\r\n        rx = Merge(rx, ry, mr, r);\r\n        return x;\r\n    }\r\n\r\n    void Query(int x, int l, int r, int a, int b, VI&amp; L) {\r\n        if (!x || b &lt; l || r &lt; a) return;\r\n        if (a &lt;= l &amp;&amp; r &lt;= b) {\r\n            L.PB(x);\r\n        } else {\r\n            Query(lc, a, b, L);\r\n            Query(rc, a, b, L);\r\n        }\r\n    }\r\n\r\n} using namespace Chairman_Tree;\r\n\r\nvoid dfs(int u = 1) {\r\n    pp = H&#x5B;u]; Init(T&#x5B;u]);\r\n    for (auto v: adj&#x5B;u]) {\r\n        dfs(v);\r\n        T&#x5B;u] = Merge(T&#x5B;u], T&#x5B;v]);\r\n    }\r\n}\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;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n, m); G.m = 2; G.s = n+m, G.t = n+m+1; tot = G.t;\r\n\r\n    FOR_1(i, 2, n) adj&#x5B;RD()].PB(i);\r\n    REP_1(i, n) RD(H&#x5B;i]); dfs();\r\n\r\n    REP(i, m) {\r\n        int l, r, d; RD(l, r, d); G.add_edge(G.s, i, RD());\r\n        VI L; Query(T&#x5B;d], 1, n, l, r, L);\r\n        for (auto l: L) G.add_edge(i, l, INF);\r\n    }\r\n\r\n    FOR_1(x, G.t+1, tot) {\r\n        if (lx) G.add_edge(x, lx, INF);\r\n        if (rx) G.add_edge(x, rx, INF);\r\n    }\r\n\r\n    G.n = tot+1;\r\n    cout &lt;&lt; G.Dinitz() &lt;&lt; endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/darkbzoj.cc\/problem\/3681 \u7f51\u7edc\u6d41\u5efa\u6a21\u4e0a\u6bd4\u4e0a\u9898\u8981\u7b80\u5355\u3002 \u51fd\u6570\u5f0f\u7ebf\u6bb5\u6811\u65b9\u9762\u9700\u8981\u7ebf\u6bb5\u6811\u5408\u5e76\u3002 \u603b\u4e4b\u8fd8\u662f\u6bd4\u4e0a\u4e00\u9898\u7b80\u5355\u3002 darkbzoj \u4e0d\u652f\u6301 cpp14\uff0c\u65e0\u6cd5\u65b9\u4fbf\u7684\u4f7f\u7528 atl\u3002\u3002\u3002\uff08\u81f3\u5c11\u6211\u4e0d\u77e5\u9053\u600e\u4e48\u6539\u3002\u3002\u3002\uff09 \u503c\u5f97\u6ce8\u610f\u7684\u662f\u5bf9\u6743\u503c\u91cd\u590d\u8282\u70b9\u7684\u5904\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u5728\u53f6\u5b50\u4f4d\u7f6e\u52a8\u6001\u521b\u5efa\u65b0\u7684\u8282\u70b9\uff0c \u628a\u65e7\u53f6\u5b50\u90fd\u5305\u542b\u5728\u5185\uff0c\u4e0d\u5f71\u54cd\u590d\u6742\u5ea6\u3002 \u53e6\u5916\u5bf9\u4e8e\u4e4b\u524d\u7684\u8fd9\u7c7b\u6811\u4e0a\u7ebf\u6bb5\u6811\u5408\u5e76\u95ee\u9898\uff0cmerge \u7684\u65f6\u5019\u6211\u4eec\u53ef\u4ee5\u7834\u574f\u6389\u4e4b\u524d\u7684\u72b6\u6001\uff0c\u8986\u76d6\u5f0f\u66f4\u65b0\u800c\u4e0d\u53bb new_node() \u4ee5\u51cf\u5c11\u5185\u5b58\u5f00\u652f\u3002 \u4f46\u662f\u8fd9\u4e2a\u9898\u91cc\u6211\u4eec\u5fc5\u987b\u533a\u522b\u51fa\u8fd9\u4e9b\u72b6\u6001\uff08\u5efa\u56fe\u7684\u65f6\u5019\u4f1a query \u5230\uff09\uff0c\u6240\u4ee5\u8fd8\u662f\u8001\u5b9e\u7684\u6bcf\u6b21\u90fd new_node() \u4e3a\u597d\u3002\u3002\u3002 const int N = int(1e4) + 9; struct Network_Flow{ const static int N = int(1e6) + 6, M = 2*N; int D&#x5B;N], hd&#x5B;N], suc&#x5B;M], to&#x5B;M], cap&#x5B;M]; int n, m, s, t; inline void add_edge(int x, int [&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-1992","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-w8","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1992","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=1992"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1992\/revisions"}],"predecessor-version":[{"id":1995,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1992\/revisions\/1995"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1992"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1992"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1992"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}