{"id":939,"date":"2014-08-08T05:37:00","date_gmt":"2014-08-07T21:37:00","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=939"},"modified":"2016-08-24T20:44:02","modified_gmt":"2016-08-24T12:44:02","slug":"spoj-3267-d-query","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/spoj-3267-d-query\/","title":{"rendered":"SPOJ 3267. D-query"},"content":{"rendered":"<p><!--more--><br \/>\nhttp:\/\/www.spoj.com\/problems\/DQUERY\/ <\/p>\n<blockquote class=\"wp-embedded-content\" data-secret=\"Opz67QIGMp\"><p><a href=\"https:\/\/www.shuizilong.com\/house\/archives\/uva-12345-dynamic-lensetalr\/\">UVa 12345. Dynamic len(set(a[L:R]))<\/a><\/p><\/blockquote>\n<p><iframe loading=\"lazy\" class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" style=\"position: absolute; clip: rect(1px, 1px, 1px, 1px);\" title=\"&#8220;UVa 12345. Dynamic len(set(a[L:R]))&#8221; &#8212; \u67d0\u5c9b\" src=\"https:\/\/www.shuizilong.com\/house\/archives\/uva-12345-dynamic-lensetalr\/embed\/#?secret=todwnDSF0o#?secret=Opz67QIGMp\" data-secret=\"Opz67QIGMp\" width=\"500\" height=\"282\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\"><\/iframe><br \/>\nhttp:\/\/www.2333333.tk\/277.html <\/p>\n<p>\u505a\u6cd5\u4e00\uff1a<br \/>\n\u79bb\u7ebf + \u6811\u72b6\u6570\u7ec4\uff1a<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(3e4) + 9, QN = int(2e5) + 9;\r\nint A&#x5B;N], pre&#x5B;N]; vector&lt;PII&gt; qry&#x5B;N];\r\nint ans&#x5B;QN], n, m;\r\n\r\nnamespace BIT{\r\n    const int N = int(3e4) + 9, M = int(2e5) + 9;\r\n    int C&#x5B;N];\r\n    void Add(int x, int d){\r\n        for (;x&lt;=n;x+=low_bit(x)) C&#x5B;x] += d;\r\n    }\r\n    int Sum(int x){\r\n        int z = 0; for (;x;x^=low_bit(x)) z += C&#x5B;x];\r\n        return z;\r\n    }\r\n} using namespace BIT;\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); VI P; REP_1(i, n) P.PB(RD(A&#x5B;i])); UNQ(P);\r\n    REP_1(i, n) A&#x5B;i] = LBD(P, A&#x5B;i]);\r\n\r\n    REP_C(i, RD(m)){\r\n        int l, r; RD(l, r);\r\n        qry&#x5B;l].PB(MP(r, i));\r\n    }\r\n\r\n#define ii pre&#x5B;A&#x5B;i]]\r\n    DWN_1(i, n, 1){\r\n        if (ii) Add(ii, -1); Add(i, 1); ii = i;\r\n        ECH(it, qry&#x5B;i]) ans&#x5B;it-&gt;se] = Sum(it-&gt;fi);\r\n    }\r\n\r\n    REP(i, m) OT(ans&#x5B;i]);\r\n}\r\n<\/pre>\n<p>\u505a\u6cd5\u4e8c\uff1a<br \/>\n\u4e3b\u5e2d\u6811\u3002\u3002\u3002<br \/>\n\u8fd9\u4e2a\u9898\u53ef\u4ee5\u770b\u505a\u662f\u4e3b\u5e2d\u6811\u7684\u5165\u95e8\u9898\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(3e4) + 9, QN = int(2e5) + 9;\r\nint T&#x5B;N], A&#x5B;N], pre&#x5B;N], n, m;\r\n\r\nnamespace ST{\r\n\r\n#define lx l&#x5B;x]\r\n#define rx r&#x5B;x]\r\n#define ly l&#x5B;y]\r\n#define ry r&#x5B;y]\r\n#define ml (ll + rr &gt;&gt; 1)\r\n#define mr (ml + 1)\r\n\r\n    const int NN = N*18 + 9;\r\n    int l&#x5B;NN], r&#x5B;NN], c&#x5B;NN], tot;\r\n\r\n    int new_node(){\r\n        return ++tot;\r\n    }\r\n\r\n    int Add(int y, int p, int d){\r\n        int x = new_node(), root = x; int ll = 1, rr = n;\r\n\r\n        c&#x5B;x] = c&#x5B;y] + d;\r\n        while (ll &lt; rr){\r\n            if (p &lt; mr){\r\n                lx = new_node(), rx = ry;\r\n                x = lx, y = ly, rr = ml;\r\n            }\r\n            else {\r\n                lx = ly, rx = new_node();\r\n                x = rx, y = ry, ll = mr;\r\n            }\r\n            c&#x5B;x] = c&#x5B;y] + d;\r\n        }\r\n        return root;\r\n    }\r\n\r\n    int Sum(int x, int p){\r\n        int z = 0, ll = 1, rr = n;\r\n        while (p != rr){\r\n            if (p &lt; mr) x = lx, rr = ml;\r\n            else z += c&#x5B;lx], x = rx, ll = mr;\r\n        }\r\n        z += c&#x5B;x];\r\n        return z;\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;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); VI P; REP_1(i, n) P.PB(RD(A&#x5B;i])); UNQ(P);\r\n    REP_1(i, n) A&#x5B;i] = LBD(P, A&#x5B;i]);\r\n\r\n#define ii pre&#x5B;A&#x5B;i]]\r\n\r\n    DWN_1(i, n, 1){\r\n        int x = T&#x5B;i+1]; if (ii) x = ST::Add(x, ii, -1); x = ST::Add(x, i, 1); ii = i;\r\n        T&#x5B;i] = x;\r\n    }\r\n\r\n    REP_C(i, RD(m)){\r\n        int l, r; RD(l, r);\r\n        OT(ST::Sum(T&#x5B;l], r));\r\n    }\r\n}\r\n\r\n<\/pre>\n<p>SPOJ 3267. D-query<br \/>\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1640753 ( Fotile \u5f0f\u3002\uff08\u4e0d\u5e38\u7528\u3002\u3002\uff09<br \/>\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1640759 ( Seter \u5f0f \u3002\u3002\uff08\u975e\u9012\u5f52\u3002\u3002\uff09<br \/>\nhttp:\/\/acm.hust.edu.cn\/vjudge\/problem\/viewSource.action?id=1640738\uff08\u79bb\u7ebf + \u6811\u72b6\u6570\u7ec4 \uff081500ms<\/p>\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":[21],"tags":[],"class_list":["post-939","post","type-post","status-publish","format-standard","hentry","category-spoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-f9","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/939","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=939"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/939\/revisions"}],"predecessor-version":[{"id":1076,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/939\/revisions\/1076"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=939"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=939"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=939"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}