{"id":1184,"date":"2015-07-22T04:48:16","date_gmt":"2015-07-21T20:48:16","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1184"},"modified":"2015-07-22T04:48:16","modified_gmt":"2015-07-21T20:48:16","slug":"bzoj-1227-sdoi2009%e8%99%94%e8%af%9a%e7%9a%84%e5%a2%93%e4%b8%bb%e4%ba%ba","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1227-sdoi2009%e8%99%94%e8%af%9a%e7%9a%84%e5%a2%93%e4%b8%bb%e4%ba%ba\/","title":{"rendered":"BZOJ 1227. [SDOI2009]\u8654\u8bda\u7684\u5893\u4e3b\u4eba"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1227\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1227<\/a><\/p>\n<p>\u79bb\u6563\u5316\u3001\u6811\u72b6\u6570\u7ec4\u3002<\/p>\n<pre class=\"brush: cpp; collapse: true; light: false; title: Sap; toolbar: true; notranslate\" title=\"Sap\">\r\n\r\nconst int N = int(1e5) + 9, K = 10 + 1;\r\n\r\nPII P&#x5B;N]; int C&#x5B;N]&#x5B;K];\r\nint L&#x5B;N], R&#x5B;N], n, k;\r\n\r\nnamespace BIT{\r\n    int S&#x5B;N];\r\n    void Add(int x){\r\n        int d = -C&#x5B;L&#x5B;x]]&#x5B;k]*C&#x5B;R&#x5B;x]]&#x5B;k] + C&#x5B;++L&#x5B;x]]&#x5B;k]*C&#x5B;--R&#x5B;x]]&#x5B;k];\r\n        for (;x&lt;=n;x+=low_bit(x)) S&#x5B;x] += d;\r\n    }\r\n    int Sum(int x){\r\n        int z = 0; for (;x;x^=low_bit(x)) z += S&#x5B;x];\r\n        return z;\r\n    }\r\n    int Sum(int l, int r){\r\n        return Sum(r) - Sum(l-1);\r\n    }\r\n} using namespace BIT;\r\n\r\nvoid init(){\r\n    int _; RD(_,_,n); REP(i, n) RD(P&#x5B;i].fi,P&#x5B;i].se); RD(k);\r\n    REP(i, n){C&#x5B;i]&#x5B;0] = 1; REP_1_C(j, min(k, i)) C&#x5B;i]&#x5B;j] = C&#x5B;i-1]&#x5B;j-1] + C&#x5B;i-1]&#x5B;j]; }\r\n\r\n    sort(P, P+n); for (int x=1,i=0;i&lt;n;++x){\r\n        int ii = i + 1; while (ii &lt; n &amp;&amp; P&#x5B;ii].fi == P&#x5B;i].fi) P&#x5B;ii++].fi = x;\r\n        P&#x5B;i].fi = x; i = ii;\r\n    }\r\n    REP(i, n){\r\n        swap(P&#x5B;i].fi, P&#x5B;i].se);\r\n        ++R&#x5B;P&#x5B;i].se];\r\n    }\r\n\r\n}\r\nint solve(){\r\n    int z = 0;\r\n    sort(P, P+n); for (int i=0;i&lt;n;){\r\n        int ii = i + 1; while (ii &lt; n &amp;&amp; P&#x5B;ii].fi == P&#x5B;i].fi) ++ii;\r\n        int a = 0, b = ii-i; FOR(j, i, ii){\r\n            if (a &gt;= k &amp;&amp; b &gt;= k) z += C&#x5B;a]&#x5B;k]*C&#x5B;b]&#x5B;k]*Sum(P&#x5B;j-1].se+1, P&#x5B;j].se-1);\r\n            Add(P&#x5B;j].se); ++a,--b;\r\n        }\r\n        i = ii;\r\n    }\r\n    return z;\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#endif\r\n\r\n    init();\r\n    OT(solve() &amp; 0x7fffffff);\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","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":[22],"tags":[],"class_list":["post-1184","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-j6","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1184","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=1184"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1184\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}