{"id":306,"date":"2010-07-17T02:38:54","date_gmt":"2010-07-16T18:38:54","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=306"},"modified":"2012-07-17T02:43:07","modified_gmt":"2012-07-16T18:43:07","slug":"poj-2155-matrix","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-2155-matrix\/","title":{"rendered":"POJ 2155. Matrix"},"content":{"rendered":"<h3>Brief description: <\/h3>\n<p>&#8230; \u7ed9\u5b9a\u4e00\u4e2a 0\/1 \u77e9\u9635\uff0c\u521d\u59cb\u5168\u662f 0\uff0c\u52a8\u6001\u7ef4\u62a4\u4ee5\u4e0b\u64cd\u4f5c\u3002<\/p>\n<ul>\n<li>C x1 y1 x2 y2: \u5c06\u4e00\u4e2a\u5b50\u77e9\u9635\u53d6\u53cd\u3002<\/li>\n<li>Q x y: \u8be2\u95ee\u5355\u4e2a\u4f4d\u7f6e\u7684\u72b6\u6001\u3002<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<h3>Analysis: <\/h3>\n<p>&#8230; \u7565\uff08\u4e8c\u7ef4\u6811\u72b6\u6570\u7ec4\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: POJ 2155. Matrix.cpp; toolbar: true; notranslate\" title=\"POJ 2155. Matrix.cpp\">\r\nconst int N = 1001;\r\nbool C&#x5B;N]&#x5B;N];\r\nint n, m;\r\n\r\nvoid Modify(int x, int y){\r\n\twhile (x &gt; 0){\r\n\t\tfor (int t = y; t &gt; 0; t -= low_bit(t))\r\n\t\t\tC&#x5B;x]&#x5B;t] ^= 1;\r\n\t\tx -= low_bit(x);\r\n\t}\r\n}\r\n\r\nbool Query(int x, int y){\r\n\tbool res = false; while (x &lt;= n){\r\n\t\tfor (int t = y; t &lt;= n; t += low_bit(t))\r\n\t\t\tres ^= C&#x5B;x]&#x5B;t];\r\n\t\tx += low_bit(x);\r\n\t}\r\n\treturn res;\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\tRush{\r\n\t\tint x1, y1, x2, y2; char cmd;\r\n\r\n\t\tRST(C); RD(n); DO_C(RD()){\r\n\t\t\tRC(cmd); if (cmd =='C'){\r\n\t\t\t\tRD(x1, y1, x2, y2);\r\n\t\t\t\tModify(x2, y2), Modify(x2, y1-1), Modify(x1-1, y2), Modify(x1-1, y1-1);\r\n\t\t\t}\r\n\t\t\telse {\r\n\t\t\t\tRD(x1, y1);\r\n\t\t\t\tOT(Query(x1, y1));\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tputs(&quot;&quot;);\r\n\t}\r\n}\r\n<\/pre>\n<h3>External link: <\/h3>\n<p><a href=\"http:\/\/poj.org\/problem?id=2155\">http:\/\/poj.org\/problem?id=2155<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brief description: &#8230; \u7ed9\u5b9a\u4e00\u4e2a 0\/1 \u77e9\u9635\uff0c\u521d\u59cb\u5168\u662f 0\uff0c\u52a8\u6001\u7ef4\u62a4\u4ee5\u4e0b\u64cd\u4f5c\u3002 C x1 y1 x2 y2: \u5c06\u4e00\u4e2a\u5b50\u77e9\u9635\u53d6\u53cd\u3002 Q x y: \u8be2\u95ee\u5355\u4e2a\u4f4d\u7f6e\u7684\u72b6\u6001\u3002<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[19],"tags":[],"class_list":["post-306","post","type-post","status-publish","format-standard","hentry","category-poj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-4W","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/306","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=306"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/306\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=306"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}