{"id":981,"date":"2014-09-27T08:00:48","date_gmt":"2014-09-27T00:00:48","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=981"},"modified":"2014-09-27T08:00:48","modified_gmt":"2014-09-27T00:00:48","slug":"bzoj-1493-noi2007%e9%a1%b9%e9%93%be%e5%b7%a5%e5%8e%82","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/bzoj-1493-noi2007%e9%a1%b9%e9%93%be%e5%b7%a5%e5%8e%82\/","title":{"rendered":"BZOJ 1493. [NOI2007]\u9879\u94fe\u5de5\u5382"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1493\">http:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1493<\/a><\/p>\n<h3>Brief description: <\/h3>\n<p>\u7565\u3002\uff09<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6d4b\u8bd5\u6a21\u677f\u3002\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/\/}\/* .................................................................................................................................. *\/\r\n \r\nconst int MAXN=500001;\r\n \r\nconst int N = int(5e5) + 9, NN = 4*N;\r\n \r\nint n;\r\n \r\nnamespace T{\r\n \r\n    int lc&#x5B;NN], rc&#x5B;NN], sc&#x5B;NN]; bool s0&#x5B;NN];\r\n    int a, b, c;\r\n \r\n#define lx (x&lt;&lt;1)\r\n#define rx (lx|1)\r\n#define ml (l+r&gt;&gt;1)\r\n#define mr (ml+1)\r\n#define lcc lx,l,ml\r\n#define rcc rx,mr,r\r\n#define rt 1, 0, n-1\r\n \r\n    void sss(int x, int c){\r\n        lc&#x5B;x] = rc&#x5B;x] = c;\r\n        sc&#x5B;x] = s0&#x5B;x] = 1;\r\n    }\r\n \r\n    void upd(int x){\r\n        lc&#x5B;x] = lc&#x5B;lx]; rc&#x5B;x] = rc&#x5B;rx];\r\n        sc&#x5B;x] = sc&#x5B;lx] + sc&#x5B;rx] - (rc&#x5B;lx] == lc&#x5B;rx]);\r\n    }\r\n \r\n    void rls(int x){\r\n        if (s0&#x5B;x]){\r\n            sss(lx, lc&#x5B;x]), sss(rx, rc&#x5B;x]);\r\n            s0&#x5B;x] = 0;\r\n        }\r\n    }\r\n \r\n    int getColor(int x, int l, int r){\r\n        if (l == r) return lc&#x5B;x];\r\n        rls(x); return a &lt; mr ? getColor(lcc) : getColor(rcc);\r\n    }\r\n \r\n    int getColor(int x){\r\n        a = x;\r\n        return getColor(rt);\r\n    }\r\n \r\n    int getCount(int x, int l, int r){\r\n        if (b &lt; l || r &lt; a) return 0;\r\n        if (a &lt;= l &amp;&amp; r &lt;= b) return sc&#x5B;x];\r\n        rls(x); int z = getCount(lcc) + getCount(rcc);\r\n        if (a &lt;= ml &amp;&amp; mr &lt;= b &amp;&amp; rc&#x5B;lx] == lc&#x5B;rx]) --z;\r\n        return z;\r\n    }\r\n \r\n    int getCount(int _a, int _b){\r\n        if (_a &lt;= _b){\r\n            a = _a, b = _b;\r\n            return getCount(rt);\r\n        }\r\n        else{\r\n            return getCount(_a,n-1) + getCount(0,_b) - (lc&#x5B;1] == rc&#x5B;1]);\r\n        }\r\n    }\r\n \r\n    void Build(int x, int l, int r){\r\n        if (l == r) sss(x, RD());\r\n        else{\r\n            s0&#x5B;x] = 0; \/\/!\r\n            Build(lcc), Build(rcc);\r\n            upd(x);\r\n        }\r\n    }\r\n \r\n    void _Paint(int x, int l, int r){\r\n        if (b &lt; l || r &lt; a) return;\r\n        if (a &lt;= l &amp;&amp; r &lt;= b) sss(x, c);\r\n        else{\r\n            rls(x);\r\n            _Paint(lcc), _Paint(rcc);\r\n            upd(x);\r\n        }\r\n    }\r\n \r\n    void Paint(int _a, int _b, int _c){\r\n \r\n        c = _c;\r\n \r\n        if (_a &lt;= _b){\r\n            a = _a, b = _b, _Paint(rt);\r\n        }\r\n        else{\r\n            a = _a, b = n-1, _Paint(rt);\r\n            a = 0, b = _b, _Paint(rt);\r\n        }\r\n    }\r\n \r\n \r\n    int offset; bool flip;\r\n    void _R(int &amp;x){if (x&lt;0) x+=n; else if (x&gt;=n) x-=n;}\r\n    void _T(int &amp;x){if (flip) x=n-x; x-=offset; _R(x);}\r\n \r\n} using namespace T;\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); RD(); Build(rt);\r\n \r\n    char cmd&#x5B;3]; int ca, cb, z, a, b; Rush{\r\n        switch (RS(cmd)&#x5B;0]){\r\n            case 'R':\r\n                if (!flip) offset += RD(); else offset -= RD();\r\n                _R(offset);\r\n                break;\r\n            case 'F':\r\n                flip = !flip;\r\n                break;\r\n            case 'S':\r\n#define get_ab() RD(a,b);--a,--b;_T(a),_T(b); if (flip)swap(a,b)\r\n                get_ab(); ca = getColor(a), cb = getColor(b);\r\n                Paint(a,a,cb), Paint(b,b,ca);\r\n                break;\r\n            case 'P':\r\n                get_ab(); RD(c);\r\n                if (a&lt;=b) Paint(a,b,c);\r\n                else Paint(a,n-1,c), Paint(0,b,c);\r\n                break;\r\n            case 'C':\r\n                if (cmd&#x5B;1]=='S'){\r\n                    get_ab();\r\n                    z = getCount(a,b);\r\n                }\r\n                else{\r\n                    z = sc&#x5B;1]; if (z&gt;1 &amp;&amp; lc&#x5B;1] == rc&#x5B;1]) --z;\r\n                }\r\n                OT(z);\r\n                break;\r\n        }\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n<p><a href=\"https:\/\/gist.github.com\/lychees\/61bc5dfa0c90ccd3901d\">https:\/\/gist.github.com\/lychees\/61bc5dfa0c90ccd3901d<\/a><\/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":[22],"tags":[],"class_list":["post-981","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fP","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/981","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=981"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/981\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=981"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=981"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=981"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}